/*
 * The backend-independent part of the reference module.
 */

#include "git-compat-util.h"
#include "advice.h"
#include "config.h"
#include "environment.h"
#include "hashmap.h"
#include "gettext.h"
#include "hex.h"
#include "lockfile.h"
#include "iterator.h"
#include "refs.h"
#include "refs/refs-internal.h"
#include "run-command.h"
#include "hook.h"
#include "object-name.h"
#include "object-store-ll.h"
#include "object.h"
#include "path.h"
#include "tag.h"
#include "submodule.h"
#include "worktree.h"
#include "strvec.h"
#include "repository.h"
#include "setup.h"
#include "sigchain.h"
#include "date.h"
#include "commit.h"
#include "wildmatch.h"

/*
 * List of all available backends
 */
static struct ref_storage_be *refs_backends = &refs_be_files;

/* Searches the list of registered ref storage backends for one with
 * the given name. Returns a pointer to the ref_storage_be if found,
 * or NULL if no match is found.
 */
static struct ref_storage_be *find_ref_storage_backend(const char *name)
{
	struct ref_storage_be *be;
	for (be = refs_backends; be; be = be->next)
		if (!strcmp(be->name, name))
			return be;
	return NULL;
}

/*
 * How to handle various characters in refnames:
 * 0: An acceptable character for refs
 * 1: End-of-component
 * 2: ., look for a preceding . to reject .. in refs
 * 3: {, look for a preceding @ to reject @{ in refs
 * 4: A bad character: ASCII control characters, and
 *    ":", "?", "[", "\", "^", "~", SP, or TAB
 * 5: *, reject unless REFNAME_REFSPEC_PATTERN is set
 */
static unsigned char refname_disposition[256] = {
	1, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
	4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
	4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 2, 1,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 4,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 4, 0, 4, 0,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 4, 4
};

struct ref_namespace_info ref_namespace[] = {
	[NAMESPACE_HEAD] = {
		.ref = "HEAD",
		.decoration = DECORATION_REF_HEAD,
		.exact = 1,
	},
	[NAMESPACE_BRANCHES] = {
		.ref = "refs/heads/",
		.decoration = DECORATION_REF_LOCAL,
	},
	[NAMESPACE_TAGS] = {
		.ref = "refs/tags/",
		.decoration = DECORATION_REF_TAG,
	},
	[NAMESPACE_REMOTE_REFS] = {
		/*
		 * The default refspec for new remotes copies refs from
		 * refs/heads/ on the remote into refs/remotes/<remote>/.
		 * As such, "refs/remotes/" has special handling.
		 */
		.ref = "refs/remotes/",
		.decoration = DECORATION_REF_REMOTE,
	},
	[NAMESPACE_STASH] = {
		/*
		 * The single ref "refs/stash" stores the latest stash.
		 * Older stashes can be found in the reflog.
		 */
		.ref = "refs/stash",
		.exact = 1,
		.decoration = DECORATION_REF_STASH,
	},
	[NAMESPACE_REPLACE] = {
		/*
		 * This namespace allows Git to act as if one object ID
		 * points to the content of another. Unlike the other
		 * ref namespaces, this one can be changed by the
		 * GIT_REPLACE_REF_BASE environment variable. This
		 * .namespace value will be overwritten in setup_git_env().
		 */
		.ref = "refs/replace/",
		.decoration = DECORATION_GRAFTED,
	},
	[NAMESPACE_NOTES] = {
		/*
		 * The refs/notes/commit ref points to the tip of a
		 * parallel commit history that adds metadata to commits
		 * in the normal history. This ref can be overwritten
		 * by the core.notesRef config variable or the
		 * GIT_NOTES_REFS environment variable.
		 */
		.ref = "refs/notes/commit",
		.exact = 1,
	},
	[NAMESPACE_PREFETCH] = {
		/*
		 * Prefetch refs are written by the background 'fetch'
		 * maintenance task. It allows faster foreground fetches
		 * by advertising these previously-downloaded tips without
		 * updating refs/remotes/ without user intervention.
		 */
		.ref = "refs/prefetch/",
	},
	[NAMESPACE_REWRITTEN] = {
		/*
		 * Rewritten refs are used by the 'label' command in the
		 * sequencer. These are particularly useful during an
		 * interactive rebase that uses the 'merge' command.
		 */
		.ref = "refs/rewritten/",
	},
};

/**
 * Updates the ref name for the given ref namespace.
 * 
 * @param namespace The ref namespace to update 
 * @param ref The new ref name for the namespace
 */
void update_ref_namespace(enum ref_namespace namespace, char *ref)
{
	struct ref_namespace_info *info = &ref_namespace[namespace];
	if (info->ref_updated)
		free(info->ref);
	info->ref = ref;
	info->ref_updated = 1;
}

/*
 * Try to read one refname component from the front of refname.
 * Return the length of the component found, or -1 if the component is
 * not legal.  It is legal if it is something reasonable to have under
 * ".git/refs/"; We do not like it if:
 *
 * - it begins with ".", or
 * - it has double dots "..", or
 * - it has ASCII control characters, or
 * - it has ":", "?", "[", "\", "^", "~", SP, or TAB anywhere, or
 * - it has "*" anywhere unless REFNAME_REFSPEC_PATTERN is set, or
 * - it ends with a "/", or
 * - it ends with ".lock", or
 * - it contains a "@{" portion
 *
 * When sanitized is not NULL, instead of rejecting the input refname
 * as an error, try to come up with a usable replacement for the input
 * refname in it.
 */
/**
 * Check if a refname component is valid.
 *
 * Tries to read one component from the front of refname and checks if it is
 * a legal refname component. Returns the length of the component found, 
 * or -1 if the component is invalid.
 *
 * A legal component must not:
 * - Start with "."
 * - Contain ".."
 * - Contain ASCII control characters 
 * - Contain ":", "?", "[", "\", "^", "~", SP, or TAB
 * - End with "/" 
 * - End with ".lock"
 * - Contain "@{"
*/
static int check_refname_component(const char *refname, int *flags,
				   struct strbuf *sanitized)
{
	const char *cp;
	char last = '\0';
	size_t component_start = 0; /* garbage - not a reasonable initial value */

	if (sanitized)
		component_start = sanitized->len;

	for (cp = refname; ; cp++) {
		int ch = *cp & 255;
		unsigned char disp = refname_disposition[ch];

		if (sanitized && disp != 1)
			strbuf_addch(sanitized, ch);

		switch (disp) {
		case 1:
			goto out;
		case 2:
			if (last == '.') { /* Refname contains "..". */
				if (sanitized)
					/* collapse ".." to single "." */
					strbuf_setlen(sanitized, sanitized->len - 1);
				else
					return -1;
			}
			break;
		case 3:
			if (last == '@') { /* Refname contains "@{". */
				if (sanitized)
					sanitized->buf[sanitized->len-1] = '-';
				else
					return -1;
			}
			break;
		case 4:
			/* forbidden char */
			if (sanitized)
				sanitized->buf[sanitized->len-1] = '-';
			else
				return -1;
			break;
		case 5:
			if (!(*flags & REFNAME_REFSPEC_PATTERN)) {
				/* refspec can't be a pattern */
				if (sanitized)
					sanitized->buf[sanitized->len-1] = '-';
				else
					return -1;
			}

			/*
			 * Unset the pattern flag so that we only accept
			 * a single asterisk for one side of refspec.
			 */
			*flags &= ~ REFNAME_REFSPEC_PATTERN;
			break;
		}
		last = ch;
	}
out:
	if (cp == refname)
		return 0; /* Component has zero length. */

	if (refname[0] == '.') { /* Component starts with '.'. */
		if (sanitized)
			sanitized->buf[component_start] = '-';
		else
			return -1;
	}
	if (cp - refname >= LOCK_SUFFIX_LEN &&
	    !memcmp(cp - LOCK_SUFFIX_LEN, LOCK_SUFFIX, LOCK_SUFFIX_LEN)) {
		if (!sanitized)
			return -1;
		/* Refname ends with ".lock". */
		while (strbuf_strip_suffix(sanitized, LOCK_SUFFIX)) {
			/* try again in case we have .lock.lock */
		}
	}
	return cp - refname;
}

/**
 * Check if a reference name conforms to the expected format, 
 * and sanitize it if needed.
 *
 * This checks if the provided refname only contains allowed
 * characters and components based on the specified flags. 
 * If sanitizing, it will replace invalid characters with
 * dashes ('-').
 *
 * @param refname The reference name to check.
 * @param flags Flags controlling behavior (e.g. allowed characters).
 * @param sanitized An optional strbuf to store the sanitized name.
 * @return 0 if valid, < 0 if invalid even after sanitizing.
 */
static int check_or_sanitize_refname(const char *refname, int flags,
				     struct strbuf *sanitized)
{
	int component_len, component_count = 0;

	if (!strcmp(refname, "@")) {
		/* Refname is a single character '@'. */
		if (sanitized)
			strbuf_addch(sanitized, '-');
		else
			return -1;
	}

	while (1) {
		if (sanitized && sanitized->len)
			strbuf_complete(sanitized, '/');

		/* We are at the start of a path component. */
		component_len = check_refname_component(refname, &flags,
							sanitized);
		if (sanitized && component_len == 0)
			; /* OK, omit empty component */
		else if (component_len <= 0)
			return -1;

		component_count++;
		if (refname[component_len] == '\0')
			break;
		/* Skip to next component. */
		refname += component_len + 1;
	}

	if (refname[component_len - 1] == '.') {
		/* Refname ends with '.'. */
		if (sanitized)
			; /* omit ending dot */
		else
			return -1;
	}
	if (!(flags & REFNAME_ALLOW_ONELEVEL) && component_count < 2)
		return -1; /* Refname has only one component. */
	return 0;
}

/**
 * Check if a reference name conforms to the expected format.
 *
 * This checks if the provided refname only contains allowed
 * characters and components based on the specified flags.
 *
 * @param refname The reference name to check.
 * @param flags Flags specifying allowed characters/components.
 * @return 0 if the name is valid, non-zero if not.
 */
int check_refname_format(const char *refname, int flags)
{
	return check_or_sanitize_refname(refname, flags, NULL);
}

/**
 * Sanitize the given refname component, writing the result to out.
 * This will replace problematic characters with dashes.
 */
void sanitize_refname_component(const char *refname, struct strbuf *out)
{
	if (check_or_sanitize_refname(refname, REFNAME_ALLOW_ONELEVEL, out))
		BUG("sanitizing refname '%s' check returned error", refname);
}

/**
 * Check if a reference name is safe for use.
 *
 * A reference name is considered safe if it only contains
 * uppercase letters, numbers, slashes, and dashes. This prevents issues with
 * special characters when interacting with the filesystem.
 * 
 * @param refname The reference name to check.
 * @return 1 if the name is safe, 0 if not.
 */
int refname_is_safe(const char *refname)
{
	const char *rest;

	if (skip_prefix(refname, "refs/", &rest)) {
		char *buf;
		int result;
		size_t restlen = strlen(rest);

		/* rest must not be empty, or start or end with "/" */
		if (!restlen || *rest == '/' || rest[restlen - 1] == '/')
			return 0;

		/*
		 * Does the refname try to escape refs/?
		 * For example: refs/foo/../bar is safe but refs/foo/../../bar
		 * is not.
		 */
		buf = xmallocz(restlen);
		result = !normalize_path_copy(buf, rest) && !strcmp(buf, rest);
		free(buf);
		return result;
	}

	do {
		if (!isupper(*refname) && *refname != '_')
			return 0;
		refname++;
	} while (*refname);
	return 1;
}

/*
 * Return true if refname, which has the specified oid and flags, can
 * be resolved to an object in the database. If the referred-to object
 * does not exist, emit a warning and return false.
 */
/**
 * Check if the given refname resolves to an existing object.
 *
 * @param refname name of the ref to check
 * @param repo the repository to check in
 * @param oid if not NULL, set to the object ID if the ref resolves to an object
 * @param flags additional flags modifying the resolve behavior
 * @return 1 if refname resolves to an object, 0 otherwise
 */
int ref_resolves_to_object(const char *refname,
			   struct repository *repo,
			   const struct object_id *oid,
			   unsigned int flags)
{
	if (flags & REF_ISBROKEN)
		return 0;
	if (!repo_has_object_file(repo, oid)) {
		error(_("%s does not point to a valid object!"), refname);
		return 0;
	}
	return 1;
}

/**
 * Resolves the given refname and returns a duplicated string of the resolved
 * reference.
 *
 * @param refs the ref_store to use for resolution
 * @param refname Name of the reference to resolve
 * @returns Duplicated string of the resolved reference name, or NULL on failure
 */
char *refs_resolve_refdup(struct ref_store *refs,
			  const char *refname, int resolve_flags,
			  struct object_id *oid, int *flags)
{
	const char *result;

	result = refs_resolve_ref_unsafe(refs, refname, resolve_flags,
					 oid, flags);
	return xstrdup_or_null(result);
}

/**
 * Resolves the given refname and returns a duplicated string of the resolved
 * ref.
 *
 * @param refname Name of the reference to resolve
 * @param resolve_flags Flags to control resolve behavior
 * @returns Duplicated string of the resolved reference name, or NULL on failure
 */
char *resolve_refdup(const char *refname, int resolve_flags,
		     struct object_id *oid, int *flags)
{
	return refs_resolve_refdup(get_main_ref_store(the_repository),
				   refname, resolve_flags,
				   oid, flags);
}

/* The argument to for_each_filter_refs */
struct for_each_ref_filter {
	const char *pattern;
	const char *prefix;
	each_ref_fn *fn;
	void *cb_data;
};

/**
 * Reads the value of the reference with the given name into oid.
 * refname: Name of the reference to read
 * resolve_flags: Flags to control resolve behavior
 * oid: Pointer to store the resolved reference value
 * flags: Pointer to store flags from resolution
 * Returns 0 on success.
 */
int read_ref_full(const char *refname, int resolve_flags, struct object_id *oid,
		  int *flags)
{
	struct ref_store *refs = get_main_ref_store(the_repository);

	if (refs_resolve_ref_unsafe(refs, refname, resolve_flags,
				    oid, flags))
		return 0;
	return -1;
}

/**
 * Reads the value of the reference with the given name into oid.
 * Returns 0 on success.
 */
int read_ref(const char *refname, struct object_id *oid)
{
	return read_ref_full(refname, RESOLVE_REF_READING, oid, NULL);
}

/**
 * Checks if a reference exists in the given ref_store.
 *
 * @param refs ref_store to check for the reference
 * @param refname Name of the reference to check for existence
 * @return 0 if the reference does not exist, non-zero if it exists
 */
int refs_ref_exists(struct ref_store *refs, const char *refname)
{
	return !!refs_resolve_ref_unsafe(refs, refname, RESOLVE_REF_READING,
					 NULL, NULL);
}

/**
 * Checks if a reference exists in the repository.
 *
 * @param refname Name of the reference to check for existence.
 * @return 0 if the reference does not exist, non-zero if it exists.
 */
int ref_exists(const char *refname)
{
	return refs_ref_exists(get_main_ref_store(the_repository), refname);
}

/**
 * Callback function passed to for_each_ref_in(). Filters refs
 * based on pattern, prefix, and callback function.
 *
 * refname: Name of current ref
 * oid: Object ID of current ref
 * flags: Flags from refs_resolve_ref_unsafe()
 * data: Pointer to struct for_each_ref_filter containing filter data
 *
 * Returns 0 if ref should be skipped, nonzero if ref should be processed.
 */
static int for_each_filter_refs(const char *refname,
				const struct object_id *oid,
				int flags, void *data)
{
	struct for_each_ref_filter *filter = data;

	if (wildmatch(filter->pattern, refname, 0))
		return 0;
	if (filter->prefix)
		skip_prefix(refname, filter->prefix, &refname);
	return filter->fn(refname, oid, flags, filter->cb_data);
}

/**
 * Peels the given object ID by dereferencing tags until the object is no
 * longer a tag. Updates the given object ID (oid) to the peeled object ID.
 * Returns a status code indicating whether the object was peeled and if so
 * what type of object it was peeled to.
 */
enum peel_status peel_object(const struct object_id *name,
			     struct object_id *oid)
{
	struct object *o = lookup_unknown_object(the_repository, name);

	if (o->type == OBJ_NONE) {
		int type = oid_object_info(the_repository, name, NULL);
		if (type < 0 || !object_as_type(o, type, 0))
			return PEEL_INVALID;
	}

	if (o->type != OBJ_TAG)
		return PEEL_NON_TAG;

	o = deref_tag_noverify(o);
	if (!o)
		return PEEL_INVALID;

	oidcpy(oid, &o->oid);
	return PEEL_PEELED;
}

struct warn_if_dangling_data {
	FILE *fp;
	const char *refname;
	const struct string_list *refnames;
	const char *msg_fmt;
};

/**
 * Callback for for_each_rawref() to warn if a symref is
 * dangling, i.e. resolves to a nonexisting ref.
 *
 * refname: Name of the symref
 * oid: Object ID symref resolves to (not used)
 * flags: REF_ISSYMREF if symref, 0 otherwise
 * cb_data: Pointer to struct warn_if_dangling_data
 *
 * Returns 0 to continue iterating refs.
 */
static int warn_if_dangling_symref(const char *refname,
				   const struct object_id *oid UNUSED,
				   int flags, void *cb_data)
{
	struct warn_if_dangling_data *d = cb_data;
	const char *resolves_to;

	if (!(flags & REF_ISSYMREF))
		return 0;

	resolves_to = resolve_ref_unsafe(refname, 0, NULL, NULL);
	if (!resolves_to
	    || (d->refname
		? strcmp(resolves_to, d->refname)
		: !string_list_has_string(d->refnames, resolves_to))) {
		return 0;
	}

	fprintf(d->fp, d->msg_fmt, refname);
	fputc('\n', d->fp);
	return 0;
}

/**
 * Warn about dangling symrefs.
 *
 * Prints warning messages to fp for the symref refname
 * using the format string msg_fmt if refname resolves
 * to a reference that is not present.
 */
void warn_dangling_symref(FILE *fp, const char *msg_fmt, const char *refname)
{
	struct warn_if_dangling_data data;

	data.fp = fp;
	data.refname = refname;
	data.refnames = NULL;
	data.msg_fmt = msg_fmt;
	for_each_rawref(warn_if_dangling_symref, &data);
}

/**
 * Warn about dangling symrefs.
 *
 * Prints warning messages to fp for all symrefs pointing to any
 * of the references in refnames that are not present.  Uses msg_fmt
 * for the messages.
 */
void warn_dangling_symrefs(FILE *fp, const char *msg_fmt,
			   const struct string_list *refnames)
{
	struct warn_if_dangling_data data;

	data.fp = fp;
	data.refname = NULL;
	data.refnames = refnames;
	data.msg_fmt = msg_fmt;
	for_each_rawref(warn_if_dangling_symref, &data);
}

/**
 * Call the given callback function for each tag ref.
 * Prefixes the ref name with the namespace prefix.
 * @param refs the ref_store to iterate over
 * @param fn callback function to invoke for each ref
 * @param cb_data data to pass to the callback function
 */
int refs_for_each_tag_ref(struct ref_store *refs, each_ref_fn fn, void *cb_data)
{
	return refs_for_each_ref_in(refs, "refs/tags/", fn, cb_data);
}

/**
 * Call the given callback function for each tag ref.
 * Prefixes the ref name with the namespace prefix.
 */
int for_each_tag_ref(each_ref_fn fn, void *cb_data)
{
	return refs_for_each_tag_ref(get_main_ref_store(the_repository), fn, cb_data);
}

/**
 * Call the given callback function for each branch ref.
 * Prefixes the ref name with the namespace prefix.
 *
 * @param refs the ref_store to iterate over
 * @param fn callback function to invoke for each ref
 * @param cb_data data to pass to the callback function
 */
int refs_for_each_branch_ref(struct ref_store *refs, each_ref_fn fn,
			     void *cb_data)
{
	return refs_for_each_ref_in(refs, "refs/heads/", fn, cb_data);
}

/**
 * Call the given callback function for each branch ref.
 * Prefixes the ref name with the namespace prefix.
 *
 * @param fn callback function to invoke for each ref
 * @param cb_data data to pass to the callback function
 */
int for_each_branch_ref(each_ref_fn fn, void *cb_data)
{
	return refs_for_each_branch_ref(get_main_ref_store(the_repository), fn, cb_data);
}

/**
 * Call the given callback function for each remote-tracking branch and tag ref.
 *
 * @param refs the ref_store to iterate over
 * @param fn callback function to invoke for each ref
 * @param cb_data data to pass to the callback function
 */
int refs_for_each_remote_ref(struct ref_store *refs, each_ref_fn fn,
			     void *cb_data)
{
	return refs_for_each_ref_in(refs, "refs/remotes/", fn, cb_data);
}

/**
 * Call the given callback function for each remote-tracking branch,
 * including both branches and tags.
 *
 * @param fn Callback function to invoke
 * @param cb_data Data to pass to the callback function
 */
int for_each_remote_ref(each_ref_fn fn, void *cb_data)
{
	return refs_for_each_remote_ref(get_main_ref_store(the_repository), fn, cb_data);
}

/**
 * Call the given callback function for the HEAD ref.
 * Prefixes the ref name with the namespace prefix.
 *
 * @param fn Callback function to invoke
 * @param cb_data Data to pass to the callback function
 */
int head_ref_namespaced(each_ref_fn fn, void *cb_data)
{
	struct strbuf buf = STRBUF_INIT;
	int ret = 0;
	struct object_id oid;
	int flag;

	strbuf_addf(&buf, "%sHEAD", get_git_namespace());
	if (!read_ref_full(buf.buf, RESOLVE_REF_READING, &oid, &flag))
		ret = fn(buf.buf, &oid, flag, cb_data);
	strbuf_release(&buf);

	return ret;
}

/**
 * Normalize a glob ref pattern by prepending the prefix if necessary
 * and stripping any trailing slashes.
 *
 * @param item the string list item to store the normalized pattern in
 * @param prefix optional prefix to prepend if pattern doesn't start with
 * "refs/"
 * @param pattern the glob ref pattern to normalize
 */
void normalize_glob_ref(struct string_list_item *item, const char *prefix,
			const char *pattern)
{
	struct strbuf normalized_pattern = STRBUF_INIT;

	if (*pattern == '/')
		BUG("pattern must not start with '/'");

	if (prefix)
		strbuf_addstr(&normalized_pattern, prefix);
	else if (!starts_with(pattern, "refs/") &&
		   strcmp(pattern, "HEAD"))
		strbuf_addstr(&normalized_pattern, "refs/");
	/*
	 * NEEDSWORK: Special case other symrefs such as REBASE_HEAD,
	 * MERGE_HEAD, etc.
	 */

	strbuf_addstr(&normalized_pattern, pattern);
	strbuf_strip_suffix(&normalized_pattern, "/");

	item->string = strbuf_detach(&normalized_pattern, NULL);
	item->util = has_glob_specials(pattern) ? NULL : item->string;
	strbuf_release(&normalized_pattern);
}

/**
 * Iterate over all refs matching the given glob pattern and call fn
 * for each ref. The search can be restricted to a given prefix.
 *
 * @param fn Callback function to invoke for each matching ref
 * @param pattern Glob pattern to match refs against
 * @param prefix Optional prefix to restrict the search to
 * @param cb_data Opaque data passed to callback function
 * @return 0 on success, non-zero on failure
 */
int for_each_glob_ref_in(each_ref_fn fn, const char *pattern,
	const char *prefix, void *cb_data)
{
	struct strbuf real_pattern = STRBUF_INIT;
	struct for_each_ref_filter filter;
	int ret;

	if (!prefix && !starts_with(pattern, "refs/"))
		strbuf_addstr(&real_pattern, "refs/");
	else if (prefix)
		strbuf_addstr(&real_pattern, prefix);
	strbuf_addstr(&real_pattern, pattern);

	if (!has_glob_specials(pattern)) {
		/* Append implied '/' '*' if not present. */
		strbuf_complete(&real_pattern, '/');
		/* No need to check for '*', there is none. */
		strbuf_addch(&real_pattern, '*');
	}

	filter.pattern = real_pattern.buf;
	filter.prefix = prefix;
	filter.fn = fn;
	filter.cb_data = cb_data;
	ret = for_each_ref(for_each_filter_refs, &filter);

	strbuf_release(&real_pattern);
	return ret;
}

/**
 * Iterate over all refs matching the given glob pattern and call fn
 * for each ref.
 *
 * @param fn Callback function to invoke for each matching ref
 * @param pattern Glob pattern to match refs against
 * @param cb_data Opaque data passed to callback function
 * @return 0 on success, non-zero on failure
 */
int for_each_glob_ref(each_ref_fn fn, const char *pattern, void *cb_data)
{
	return for_each_glob_ref_in(fn, pattern, NULL, cb_data);
}

/**
 * Prettify a refname by removing the leading "refs/" prefix and replacing it
 * with nicer names for well known refs.
 *
 * @param name The refname to prettify
 * @return The prettified refname
 */
const char *prettify_refname(const char *name)
{
	if (skip_prefix(name, "refs/heads/", &name) ||
	    skip_prefix(name, "refs/tags/", &name) ||
	    skip_prefix(name, "refs/remotes/", &name))
		; /* nothing */
	return name;
}

static const char *ref_rev_parse_rules[] = {
	"%.*s",
	"refs/%.*s",
	"refs/tags/%.*s",
	"refs/heads/%.*s",
	"refs/remotes/%.*s",
	"refs/remotes/%.*s/HEAD",
	NULL
};

#define NUM_REV_PARSE_RULES (ARRAY_SIZE(ref_rev_parse_rules) - 1)

/*
 * Is it possible that the caller meant full_name with abbrev_name?
 * If so return a non-zero value to signal "yes"; the magnitude of
 * the returned value gives the precedence used for disambiguation.
 *
 * If abbrev_name cannot mean full_name, return 0.
 */
/**
 * Check if a refname abbreviation could refer to the full refname.
 *
 * This checks if the given abbreviation abbrev_name could be an
 * abbreviated form of the full refname full_name. It does this by
 * trying to match abbrev_name against the rules in ref_rev_parse_rules.
 *
 * Returns a non-zero value if it's possible for them to match,
 * with higher values indicating a higher precedence match.
 * Returns 0 if it's not possible for them to match.
 */
int refname_match(const char *abbrev_name, const char *full_name)
{
	const char **p;
	const int abbrev_name_len = strlen(abbrev_name);
	const int num_rules = NUM_REV_PARSE_RULES;

	for (p = ref_rev_parse_rules; *p; p++)
		if (!strcmp(full_name, mkpath(*p, abbrev_name_len, abbrev_name)))
			return &ref_rev_parse_rules[num_rules] - p;

	return 0;
}

/*
 * Given a 'prefix' expand it by the rules in 'ref_rev_parse_rules' and add
 * the results to 'prefixes'
 */
/**
 * Expand a refname prefix using the rules in ref_rev_parse_rules and
 * add the results to 'prefixes'.
 *
 * prefixes: The strvec to add expanded prefixes to.
 * prefix: The prefix to expand according to the rules.
 */
void expand_ref_prefix(struct strvec *prefixes, const char *prefix)
{
	const char **p;
	int len = strlen(prefix);

	for (p = ref_rev_parse_rules; *p; p++)
		strvec_pushf(prefixes, *p, len, prefix);
}

static const char default_branch_name_advice[] = N_(
"Using '%s' as the name for the initial branch. This default branch name\n"
"is subject to change. To configure the initial branch name to use in all\n"
"of your new repositories, which will suppress this warning, call:\n"
"\n"
"\tgit config --global init.defaultBranch <name>\n"
"\n"
"Names commonly chosen instead of 'master' are 'main', 'trunk' and\n"
"'development'. The just-created branch can be renamed via this command:\n"
"\n"
"\tgit branch -m <name>\n"
);

/**
 * Returns the default branch name for the given repository.
 *
 * r: the repository
 * quiet: whether to suppress advice about changing the default branch name
 *
 * Returns a pointer to the default branch name string.
 */
char *repo_default_branch_name(struct repository *r, int quiet)
{
	const char *config_key = "init.defaultbranch";
	const char *config_display_key = "init.defaultBranch";
	char *ret = NULL, *full_ref;
	const char *env = getenv("GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME");

	if (env && *env)
		ret = xstrdup(env);
	else if (repo_config_get_string(r, config_key, &ret) < 0)
		die(_("could not retrieve `%s`"), config_display_key);

	if (!ret) {
		ret = xstrdup("master");
		if (!quiet)
			advise(_(default_branch_name_advice), ret);
	}

	full_ref = xstrfmt("refs/heads/%s", ret);
	if (check_refname_format(full_ref, 0))
		die(_("invalid branch name: %s = %s"), config_display_key, ret);
	free(full_ref);

	return ret;
}

/**
 * Returns the default branch name for the repository.
 *
 * quiet: whether to suppress advice about changing the default branch name
 *
 * Returns a pointer to the default branch name string.
 */
const char *git_default_branch_name(int quiet)
{
	static char *ret;

	if (!ret)
		ret = repo_default_branch_name(the_repository, quiet);

	return ret;
}

/*
 * *string and *len will only be substituted, and *string returned (for
 * later free()ing) if the string passed in is a magic short-hand form
 * to name a branch.
 */
/**
 * Substitutes a branch name if the given string is a magic short-hand
 * form. This allows the user to specify something like "main" instead
 * of "refs/heads/main".
 *
 * r: the repository
 * string: pointer to the string to check
 * len: pointer to the length of the string
 *
 * Returns a substituted string that must be freed by the caller,
 * or NULL if no substitution was made.
 */
static char *substitute_branch_name(struct repository *r,
				    const char **string, int *len,
				    int nonfatal_dangling_mark)
{
	struct strbuf buf = STRBUF_INIT;
	struct interpret_branch_name_options options = {
		.nonfatal_dangling_mark = nonfatal_dangling_mark
	};
	int ret = repo_interpret_branch_name(r, *string, *len, &buf, &options);

	if (ret == *len) {
		size_t size;
		*string = strbuf_detach(&buf, &size);
		*len = size;
		return (char *)*string;
	}

	return NULL;
}

/**
 * Tries to resolve str as a reference name in the given repository,
 * using various heuristics.
 *
 * r: the repository to look in
 * str: the string to try to resolve as a ref name
 * len: the length of str
 *
 * Returns the number of refs matched. If a single unambiguous ref is found,
 * information about it is filled into the oid and ref out-parameters.
 */
int repo_dwim_ref(struct repository *r, const char *str, int len,
		  struct object_id *oid, char **ref, int nonfatal_dangling_mark)
{
	char *last_branch = substitute_branch_name(r, &str, &len,
						   nonfatal_dangling_mark);
	int   refs_found  = expand_ref(r, str, len, oid, ref);
	free(last_branch);
	return refs_found;
}

/**
 * Expands a reference name by trying various rules and returning the SHA-1 if
 * a single unambiguous reference is found.
 *
 * This takes a repository, a reference name, the length of the name,
 * and pointers to store the SHA-1 and expanded reference if found. It tries
 * rules like prepending 'refs/heads/' to find references.
 *
 * Returns the number of references matched.
 */
int expand_ref(struct repository *repo, const char *str, int len,
	       struct object_id *oid, char **ref)
{
	const char **p, *r;
	int refs_found = 0;
	struct strbuf fullref = STRBUF_INIT;

	*ref = NULL;
	for (p = ref_rev_parse_rules; *p; p++) {
		struct object_id oid_from_ref;
		struct object_id *this_result;
		int flag;
		struct ref_store *refs = get_main_ref_store(repo);

		this_result = refs_found ? &oid_from_ref : oid;
		strbuf_reset(&fullref);
		strbuf_addf(&fullref, *p, len, str);
		r = refs_resolve_ref_unsafe(refs, fullref.buf,
					    RESOLVE_REF_READING,
					    this_result, &flag);
		if (r) {
			if (!refs_found++)
				*ref = xstrdup(r);
			if (!warn_ambiguous_refs)
				break;
		} else if ((flag & REF_ISSYMREF) && strcmp(fullref.buf, "HEAD")) {
			warning(_("ignoring dangling symref %s"), fullref.buf);
		} else if ((flag & REF_ISBROKEN) && strchr(fullref.buf, '/')) {
			warning(_("ignoring broken ref %s"), fullref.buf);
		}
	}
	strbuf_release(&fullref);
	return refs_found;
}

/**
 * Tries to find the commit log for the given ref.
 * This function takes a repository, a ref name, the length of the ref name,
 * and pointers to store the commit SHA-1 and ref log path if found. It tries
 * various rules to find a reflog that can serve as the log for the given ref.
 */
int repo_dwim_log(struct repository *r, const char *str, int len,
		  struct object_id *oid, char **log)
{
	struct ref_store *refs = get_main_ref_store(r);
	char *last_branch = substitute_branch_name(r, &str, &len, 0);
	const char **p;
	int logs_found = 0;
	struct strbuf path = STRBUF_INIT;

	*log = NULL;
	for (p = ref_rev_parse_rules; *p; p++) {
		struct object_id hash;
		const char *ref, *it;

		strbuf_reset(&path);
		strbuf_addf(&path, *p, len, str);
		ref = refs_resolve_ref_unsafe(refs, path.buf,
					      RESOLVE_REF_READING,
					      oid ? &hash : NULL, NULL);
		if (!ref)
			continue;
		if (refs_reflog_exists(refs, path.buf))
			it = path.buf;
		else if (strcmp(ref, path.buf) &&
			 refs_reflog_exists(refs, ref))
			it = ref;
		else
			continue;
		if (!logs_found++) {
			*log = xstrdup(it);
			if (oid)
				oidcpy(oid, &hash);
		}
		if (!warn_ambiguous_refs)
			break;
	}
	strbuf_release(&path);
	free(last_branch);
	return logs_found;
}

/**
 * Tries to find the commit log for the given ref.
 *
 * This will try various rules for finding a reflog to use as the log
 * for the given refname. For example, it may use a remote-tracking
 * branch reflog if the branch is set to track a remote branch.
 *
 * @param str the refname to find the log for
 * @param len the length of str
 * @param oid pointer to store the commit OID for the log ref
 * @param log pointer to store the log ref name
 * @return number of logs found
 */
int dwim_log(const char *str, int len, struct object_id *oid, char **log)
{
	return repo_dwim_log(the_repository, str, len, oid, log);
}

/**
 * Checks if the given refname refers to a per-worktree ref.
 *
 * Per-worktree refs have names like "refs/worktrees/<wt>/foo".
 *
 * Returns 1 if the refname refers to a per-worktree ref, 0 otherwise.
 */
int is_per_worktree_ref(const char *refname)
{
	return starts_with(refname, "refs/worktree/") ||
	       starts_with(refname, "refs/bisect/") ||
	       starts_with(refname, "refs/rewritten/");
}

/**
 * Checks if the given refname has pseudoref syntax, meaning it consists
 * only of uppercase letters, dashes, and underscores. This is used to
 * identify special refs like HEAD that don't point to real objects.
 */
static int is_pseudoref_syntax(const char *refname)
{
	const char *c;

	for (c = refname; *c; c++) {
		if (!isupper(*c) && *c != '-' && *c != '_')
			return 0;
	}

	/*
	 * HEAD is not a pseudoref, but it certainly uses the
	 * pseudoref syntax.
	 */
	return 1;
}

/**
 * Checks if the given refname refers to the currently active worktree.
 *
 * Returns 1 if the refname refers to the current worktree, 0 otherwise.
 */
static int is_current_worktree_ref(const char *ref)
{
	return is_pseudoref_syntax(ref) || is_per_worktree_ref(ref);
}

/**
 * Parses the given refname to determine if it is a per-worktree ref and if so,
 * what kind. This will set the output parameters worktree_name,
 * worktree_name_length, and bare_refname accordingly.
 *
 * Returns one of the REF_WORKTREE_* constants.
 */
enum ref_worktree_type parse_worktree_ref(const char *maybe_worktree_ref,
					  const char **worktree_name, int *worktree_name_length,
					  const char **bare_refname)
{
	const char *name_dummy;
	int name_length_dummy;
	const char *ref_dummy;

	if (!worktree_name)
		worktree_name = &name_dummy;
	if (!worktree_name_length)
		worktree_name_length = &name_length_dummy;
	if (!bare_refname)
		bare_refname = &ref_dummy;

	if (skip_prefix(maybe_worktree_ref, "worktrees/", bare_refname)) {
		const char *slash = strchr(*bare_refname, '/');

		*worktree_name = *bare_refname;
		if (!slash) {
			*worktree_name_length = strlen(*worktree_name);

			/* This is an error condition, and the caller tell because the bare_refname is "" */
			*bare_refname = *worktree_name + *worktree_name_length;
			return REF_WORKTREE_OTHER;
		}

		*worktree_name_length = slash - *bare_refname;
		*bare_refname = slash + 1;

		if (is_current_worktree_ref(*bare_refname))
			return REF_WORKTREE_OTHER;
	}

	*worktree_name = NULL;
	*worktree_name_length = 0;

	if (skip_prefix(maybe_worktree_ref, "main-worktree/", bare_refname)
	    && is_current_worktree_ref(*bare_refname))
		return REF_WORKTREE_MAIN;

	*bare_refname = maybe_worktree_ref;
	if (is_current_worktree_ref(maybe_worktree_ref))
		return REF_WORKTREE_CURRENT;

	return REF_WORKTREE_SHARED;
}

/**
 * Gets the timeout in milliseconds for locking files references.
 *
 * The default timeout is 100 ms. This function gets the configured
 * timeout from the Git config setting `core.filesreflocktimeout`.
 *
 * @return Timeout in milliseconds for locking files references.
 */
long get_files_ref_lock_timeout_ms(void)
{
	static int configured = 0;

	/* The default timeout is 100 ms: */
	static int timeout_ms = 100;

	if (!configured) {
		git_config_get_int("core.filesreflocktimeout", &timeout_ms);
		configured = 1;
	}

	return timeout_ms;
}

/**
 * Deletes the reference in the given ref_store.
 *
 * @param refs the ref_store containing the reference to delete
 * @param msg the message describing the reason for deleting
 * @param refname the name of the reference to delete
 */
int refs_delete_ref(struct ref_store *refs, const char *msg,
		    const char *refname,
		    const struct object_id *old_oid,
		    unsigned int flags)
{
	struct ref_transaction *transaction;
	struct strbuf err = STRBUF_INIT;

	transaction = ref_store_transaction_begin(refs, &err);
	if (!transaction ||
	    ref_transaction_delete(transaction, refname, old_oid,
				   flags, msg, &err) ||
	    ref_transaction_commit(transaction, &err)) {
		error("%s", err.buf);
		ref_transaction_free(transaction);
		strbuf_release(&err);
		return 1;
	}
	ref_transaction_free(transaction);
	strbuf_release(&err);
	return 0;
}

/**
 * Deletes the reference with the given name.
 *
 * @param msg Message describing the reason for deleting the reference.
 * @param refname Name of the reference to delete.
 */
int delete_ref(const char *msg, const char *refname,
	       const struct object_id *old_oid, unsigned int flags)
{
	return refs_delete_ref(get_main_ref_store(the_repository), msg, refname,
			       old_oid, flags);
}

/**
 * Copies a reflog message into the given strbuf, normalizing whitespace.
 *
 * @param sb Destination strbuf to write the normalized message into.
 * @param msg The original reflog message string to normalize.
 */
static void copy_reflog_msg(struct strbuf *sb, const char *msg)
{
	char c;
	int wasspace = 1;

	while ((c = *msg++)) {
		if (wasspace && isspace(c))
			continue;
		wasspace = isspace(c);
		if (wasspace)
			c = ' ';
		strbuf_addch(sb, c);
	}
	strbuf_rtrim(sb);
}

/**
 * Normalizes a reflog message by removing extra whitespace.
 *
 * @param msg The original reflog message string.
 * @return The normalized reflog message string with extra whitespace removed.
 */
static char *normalize_reflog_message(const char *msg)
{
	struct strbuf sb = STRBUF_INIT;

	if (msg && *msg)
		copy_reflog_msg(&sb, msg);
	return strbuf_detach(&sb, NULL);
}

/**
 * Checks if a reflog should be automatically created for the given refname.
 *
 * @param refname name of the reference to check
 * @return non-zero if a reflog should be created, zero otherwise
 */
int should_autocreate_reflog(const char *refname)
{
	switch (log_all_ref_updates) {
	case LOG_REFS_ALWAYS:
		return 1;
	case LOG_REFS_NORMAL:
		return starts_with(refname, "refs/heads/") ||
			starts_with(refname, "refs/remotes/") ||
			starts_with(refname, "refs/notes/") ||
			!strcmp(refname, "HEAD");
	default:
		return 0;
	}
}

/**
 * Checks if the given reference name is a branch.
 *
 * @param refname name of the reference to check
 * @return non-zero if refname is a branch, zero otherwise
 */
int is_branch(const char *refname)
{
	return !strcmp(refname, "HEAD") || starts_with(refname, "refs/heads/");
}

struct read_ref_at_cb {
	const char *refname;
	timestamp_t at_time;
	int cnt;
	int reccnt;
	struct object_id *oid;
	int found_it;

	struct object_id ooid;
	struct object_id noid;
	int tz;
	timestamp_t date;
	char **msg;
	timestamp_t *cutoff_time;
	int *cutoff_tz;
	int *cutoff_cnt;
};

/**
 * Set the cutoff values in the callback data structure.
 *
 * This stores the cutoff time, timezone, and count values
 * in the read_ref_at_cb struct passed to the callback.
 *
 * @param cb the callback data structure
 * @param timestamp the cutoff timestamp
 */
static void set_read_ref_cutoffs(struct read_ref_at_cb *cb,
		timestamp_t timestamp, int tz, const char *message)
{
	if (cb->msg)
		*cb->msg = xstrdup(message);
	if (cb->cutoff_time)
		*cb->cutoff_time = timestamp;
	if (cb->cutoff_tz)
		*cb->cutoff_tz = tz;
	if (cb->cutoff_cnt)
		*cb->cutoff_cnt = cb->reccnt;
}

/**
 * Callback for refs_for_each_reflog_ent() to process a reflog
 * entry. Used to find the value of a ref at a specific point in time.
 *
 * @param ooid OID of the old value for the ref
 * @param noid OID of the new value for the ref
 */
static int read_ref_at_ent(struct object_id *ooid, struct object_id *noid,
			   const char *email UNUSED,
			   timestamp_t timestamp, int tz,
			   const char *message, void *cb_data)
{
	struct read_ref_at_cb *cb = cb_data;
	int reached_count;

	cb->tz = tz;
	cb->date = timestamp;

	/*
	 * It is not possible for cb->cnt == 0 on the first iteration because
	 * that special case is handled in read_ref_at().
	 */
	if (cb->cnt > 0)
		cb->cnt--;
	reached_count = cb->cnt == 0 && !is_null_oid(ooid);
	if (timestamp <= cb->at_time || reached_count) {
		set_read_ref_cutoffs(cb, timestamp, tz, message);
		/*
		 * we have not yet updated cb->[n|o]oid so they still
		 * hold the values for the previous record.
		 */
		if (!is_null_oid(&cb->ooid) && !oideq(&cb->ooid, noid))
			warning(_("log for ref %s has gap after %s"),
					cb->refname, show_date(cb->date, cb->tz, DATE_MODE(RFC2822)));
		if (reached_count)
			oidcpy(cb->oid, ooid);
		else if (!is_null_oid(&cb->ooid) || cb->date == cb->at_time)
			oidcpy(cb->oid, noid);
		else if (!oideq(noid, cb->oid))
			warning(_("log for ref %s unexpectedly ended on %s"),
				cb->refname, show_date(cb->date, cb->tz,
						       DATE_MODE(RFC2822)));
		cb->found_it = 1;
	}
	cb->reccnt++;
	oidcpy(&cb->ooid, ooid);
	oidcpy(&cb->noid, noid);
	return cb->found_it;
}

/**
 * Callback for refs_for_each_reflog_ent() to get the newest
 * reflog entry for the given ref.
 *
 * @param ooid OID of the old value for the ref
 */
static int read_ref_at_ent_newest(struct object_id *ooid UNUSED,
				  struct object_id *noid,
				  const char *email UNUSED,
				  timestamp_t timestamp, int tz,
				  const char *message, void *cb_data)
{
	struct read_ref_at_cb *cb = cb_data;

	set_read_ref_cutoffs(cb, timestamp, tz, message);
	oidcpy(cb->oid, noid);
	/* We just want the first entry */
	return 1;
}

/**
 * Callback for refs_for_each_reflog_ent_reverse() to get the oldest
 * reflog entry for the given ref.
 *
 * @param ooid OID of the old value for the ref
 * @param noid OID of the new value for the ref
 */
static int read_ref_at_ent_oldest(struct object_id *ooid,
				  struct object_id *noid,
				  const char *email UNUSED,
				  timestamp_t timestamp, int tz,
				  const char *message, void *cb_data)
{
	struct read_ref_at_cb *cb = cb_data;

	set_read_ref_cutoffs(cb, timestamp, tz, message);
	oidcpy(cb->oid, ooid);
	if (is_null_oid(cb->oid))
		oidcpy(cb->oid, noid);
	/* We just want the first entry */
	return 1;
}

/**
 * Read reflog entries for the given ref at the specified time.
 *
 * @param refs the ref_store to read from
 * @param refname name of the ref to read (e.g. "refs/heads/master")
 * @param at_time only return reflog entries at this exact timestamp
 */
int read_ref_at(struct ref_store *refs, const char *refname,
		unsigned int flags, timestamp_t at_time, int cnt,
		struct object_id *oid, char **msg,
		timestamp_t *cutoff_time, int *cutoff_tz, int *cutoff_cnt)
{
	struct read_ref_at_cb cb;

	memset(&cb, 0, sizeof(cb));
	cb.refname = refname;
	cb.at_time = at_time;
	cb.cnt = cnt;
	cb.msg = msg;
	cb.cutoff_time = cutoff_time;
	cb.cutoff_tz = cutoff_tz;
	cb.cutoff_cnt = cutoff_cnt;
	cb.oid = oid;

	if (cb.cnt == 0) {
		refs_for_each_reflog_ent_reverse(refs, refname, read_ref_at_ent_newest, &cb);
		return 0;
	}

	refs_for_each_reflog_ent_reverse(refs, refname, read_ref_at_ent, &cb);

	if (!cb.reccnt) {
		if (flags & GET_OID_QUIETLY)
			exit(128);
		else
			die(_("log for %s is empty"), refname);
	}
	if (cb.found_it)
		return 0;

	refs_for_each_reflog_ent(refs, refname, read_ref_at_ent_oldest, &cb);

	return 1;
}

/**
 * Begin a reference transaction on the given reference store.
 * Allocates a new ref_transaction, initializes it with the given
 * reference store, and returns it. This gets a transaction ready
 * for updates to be added to it via calls to ref_transaction_add_update()
 * etc.
 */
struct ref_transaction *ref_store_transaction_begin(struct ref_store *refs,
						    struct strbuf *err)
{
	struct ref_transaction *tr;
	assert(err);

	CALLOC_ARRAY(tr, 1);
	tr->ref_store = refs;
	return tr;
}

/**
 * Begin a reference transaction.
 *
 * This function initializes a new reference transaction structure,
 * which can be used to group reference updates into an atomic
 * transaction. The returned transaction handle should be freed
 * via ref_transaction_free() when no longer needed.
 *
 * @param err A strbuf for returning error messages, which must not be NULL
 * @return A new reference transaction handle, or NULL if a fatal
 *     error occurred.
 */
struct ref_transaction *ref_transaction_begin(struct strbuf *err)
{
	return ref_store_transaction_begin(get_main_ref_store(the_repository), err);
}

/**
 * Free a reference transaction, cleaning up associated data.
 *
 * Frees memory associated with the given reference transaction. This cleans
 * up the transaction's list of updates, freeing each update's message in
 * the process.
 *
 * The transaction must not be in the PREPARED state, or else the behavior
 * is undefined.
 */
void ref_transaction_free(struct ref_transaction *transaction)
{
	size_t i;

	if (!transaction)
		return;

	switch (transaction->state) {
	case REF_TRANSACTION_OPEN:
	case REF_TRANSACTION_CLOSED:
		/* OK */
		break;
	case REF_TRANSACTION_PREPARED:
		BUG("free called on a prepared reference transaction");
		break;
	default:
		BUG("unexpected reference transaction state");
		break;
	}

	for (i = 0; i < transaction->nr; i++) {
		free(transaction->updates[i]->msg);
		free(transaction->updates[i]);
	}
	free(transaction->updates);
	free(transaction);
}

/**
 * Add a reference update to the given reference transaction.
 *
 * This function adds a new reference update to the provided
 * ref_transaction. It initializes a new ref_update struct with
 * the given parameters.
 */
struct ref_update *
ref_transaction_add_update(
		struct ref_transaction *transaction,
		const char *refname, unsigned int flags,
		const struct object_id *new_oid,
		const struct object_id *old_oid,
		const char *msg)
{
	struct ref_update *update;

	if (transaction->state != REF_TRANSACTION_OPEN)
		BUG("update called for transaction that is not open");

	FLEX_ALLOC_STR(update, refname, refname);
	ALLOC_GROW(transaction->updates, transaction->nr + 1, transaction->alloc);
	transaction->updates[transaction->nr++] = update;

	update->flags = flags;

	if (flags & REF_HAVE_NEW)
		oidcpy(&update->new_oid, new_oid);
	if (flags & REF_HAVE_OLD)
		oidcpy(&update->old_oid, old_oid);
	update->msg = normalize_reflog_message(msg);
	return update;
}

/**
 * Update a reference transaction with a new reference update.
 *
 * This adds a reference update to the given reference transaction.
 * The refname, new_oid, old_oid, flags and msg parameters specify
 * the reference update to add.
 *
 * Returns 0 on success, non-zero on failure.
 */
int ref_transaction_update(struct ref_transaction *transaction,
			   const char *refname,
			   const struct object_id *new_oid,
			   const struct object_id *old_oid,
			   unsigned int flags, const char *msg,
			   struct strbuf *err)
{
	assert(err);

	if (!(flags & REF_SKIP_REFNAME_VERIFICATION) &&
	    ((new_oid && !is_null_oid(new_oid)) ?
		     check_refname_format(refname, REFNAME_ALLOW_ONELEVEL) :
			   !refname_is_safe(refname))) {
		strbuf_addf(err, _("refusing to update ref with bad name '%s'"),
			    refname);
		return -1;
	}

	if (flags & ~REF_TRANSACTION_UPDATE_ALLOWED_FLAGS)
		BUG("illegal flags 0x%x passed to ref_transaction_update()", flags);

	/*
	 * Clear flags outside the allowed set; this should be a noop because
	 * of the BUG() check above, but it works around a -Wnonnull warning
	 * with some versions of "gcc -O3".
	 */
	flags &= REF_TRANSACTION_UPDATE_ALLOWED_FLAGS;

	flags |= (new_oid ? REF_HAVE_NEW : 0) | (old_oid ? REF_HAVE_OLD : 0);

	ref_transaction_add_update(transaction, refname, flags,
				   new_oid, old_oid, msg);
	return 0;
}

/**
 * Create a new ref transaction structure.
 *
 * Allocates a new ref_transaction, initializes it with
 * ref_transaction_init(), and returns it.
 */
int ref_transaction_create(struct ref_transaction *transaction,
			   const char *refname,
			   const struct object_id *new_oid,
			   unsigned int flags, const char *msg,
			   struct strbuf *err)
{
	if (!new_oid || is_null_oid(new_oid)) {
		strbuf_addf(err, "'%s' has a null OID", refname);
		return 1;
	}
	return ref_transaction_update(transaction, refname, new_oid,
				      null_oid(), flags, msg, err);
}

/**
 * Delete a ref as part of a ref transaction.
 *
 * This function deletes the ref specified by refname, verifying that
 * the ref previously contained old_oid. It is used as part of a ref
 * transaction to delete refs.
 *
 * Parameters:
 *  transaction: the ref transaction
 *  refname: the name of the ref to delete
 *  old_oid: the expected ID that the ref previously contained
 *  flags: additional options controlling the delete process
 *  msg: explanation for why the ref was deleted
 *  err: strbuf to receive any error messages
 */
int ref_transaction_delete(struct ref_transaction *transaction,
			   const char *refname,
			   const struct object_id *old_oid,
			   unsigned int flags, const char *msg,
			   struct strbuf *err)
{
	if (old_oid && is_null_oid(old_oid))
		BUG("delete called with old_oid set to zeros");
	return ref_transaction_update(transaction, refname,
				      null_oid(), old_oid,
				      flags, msg, err);
}

/**
 * Verify that a ref exists as part of a ref transaction.
 *
 * This function checks that the specified ref exists and matches
 * the provided old_oid as part of the given ref transaction. It is
 * used to verify the state of a ref before updating or deleting it.
 *
 * @param transaction the ref transaction
 * @param refname the name of the ref to verify
 * @param old_oid the expected ID for the ref
 * @param flags additional options controlling the update process
 * @param err strbuf to receive error messages
 * @return 0 on success, non-zero on failure
 */
int ref_transaction_verify(struct ref_transaction *transaction,
			   const char *refname,
			   const struct object_id *old_oid,
			   unsigned int flags,
			   struct strbuf *err)
{
	if (!old_oid)
		BUG("verify called with old_oid set to NULL");
	return ref_transaction_update(transaction, refname,
				      NULL, old_oid,
				      flags, NULL, err);
}

/**
 * Update the object name stored in a ref.
 *
 * This function updates the ref specified by refname to point to
 * the provided new_oid object ID, after checking that the ref
 * previously contained old_oid.
 *
 * Parameters:
 *  refs: the ref_store containing the ref to update
 *  msg: the explanation for why the ref was updated
 *  refname: the name of the ref to update
 *  new_oid: the new object ID to point the ref to
 *  old_oid: the expected current object ID for the ref
 *  flags: options controlling the update process
 *
 */
int refs_update_ref(struct ref_store *refs, const char *msg,
		    const char *refname, const struct object_id *new_oid,
		    const struct object_id *old_oid, unsigned int flags,
		    enum action_on_err onerr)
{
	struct ref_transaction *t = NULL;
	struct strbuf err = STRBUF_INIT;
	int ret = 0;

	t = ref_store_transaction_begin(refs, &err);
	if (!t ||
	    ref_transaction_update(t, refname, new_oid, old_oid, flags, msg,
				   &err) ||
	    ref_transaction_commit(t, &err)) {
		ret = 1;
		ref_transaction_free(t);
	}
	if (ret) {
		const char *str = _("update_ref failed for ref '%s': %s");

		switch (onerr) {
		case UPDATE_REFS_MSG_ON_ERR:
			error(str, refname, err.buf);
			break;
		case UPDATE_REFS_DIE_ON_ERR:
			die(str, refname, err.buf);
			break;
		case UPDATE_REFS_QUIET_ON_ERR:
			break;
		}
		strbuf_release(&err);
		return 1;
	}
	strbuf_release(&err);
	if (t)
		ref_transaction_free(t);
	return 0;
}

/**
 * Update the object name stored in a ref safely.
 *
 * This function updates the ref specified by refname to point to the
 * provided new_oid object ID, provided that refname used to point to
 * old_oid previously.  If successful, the ref will be updated to point
 * to the new object ID.
 *
 * The parameters msg, refname, new_oid, and old_oid correspond to the
 * parameters of the same name to refs_update_ref().  See that function
 * for more details.
 *
 * Return 0 on success or non-zero on failure.
 */
int update_ref(const char *msg, const char *refname,
	       const struct object_id *new_oid,
	       const struct object_id *old_oid,
	       unsigned int flags, enum action_on_err onerr)
{
	return refs_update_ref(get_main_ref_store(the_repository), msg, refname, new_oid,
			       old_oid, flags, onerr);
}

/*
 * Check that the string refname matches a rule of the form
 * "{prefix}%.*s{suffix}". So "foo/bar/baz" would match the rule
 * "foo/%.*s/baz", and return the string "bar".
 */
/**
 * Check if the given refname matches the given parse rule.
 *
 * A parse rule has the form "{prefix}%.*s{suffix}", which would match
 * "prefix/content/suffix". This function checks if refname matches
 * rule, and if so returns a pointer to the "content" part of refname.
 * It also stores the length of the content part in len if len is not
 * NULL.
 */
static const char *match_parse_rule(const char *refname, const char *rule,
				    size_t *len)
{
	/*
	 * Check that rule matches refname up to the first percent in the rule.
	 * We can bail immediately if not, but otherwise we leave "rule" at the
	 * %-placeholder, and "refname" at the start of the potential matched
	 * name.
	 */
	while (*rule != '%') {
		if (!*rule)
			BUG("rev-parse rule did not have percent");
		if (*refname++ != *rule++)
			return NULL;
	}

	/*
	 * Check that our "%" is the expected placeholder. This assumes there
	 * are no other percents (placeholder or quoted) in the string, but
	 * that is sufficient for our rev-parse rules.
	 */
	if (!skip_prefix(rule, "%.*s", &rule))
		return NULL;

	/*
	 * And now check that our suffix (if any) matches.
	 */
	if (!strip_suffix(refname, rule, len))
		return NULL;

	return refname; /* len set by strip_suffix() */
}

/**
 * Shorten refname to an unambiguous abbreviation, if possible.
 *
 * Try to shorten the given refname to a unique abbreviation by
 * using the hard-coded set of rules.
 *
 * @param refs the ref_store to check for ambiguity
 * @param refname the full ref name to shorten
 * @param strict whether to fail if refname is ambiguous even
 *               if a rule matches.
 * @return the shortened ref name or NULL if no rule matched.
 */
char *refs_shorten_unambiguous_ref(struct ref_store *refs,
				   const char *refname, int strict)
{
	int i;
	struct strbuf resolved_buf = STRBUF_INIT;

	/* skip first rule, it will always match */
	for (i = NUM_REV_PARSE_RULES - 1; i > 0 ; --i) {
		int j;
		int rules_to_fail = i;
		const char *short_name;
		size_t short_name_len;

		short_name = match_parse_rule(refname, ref_rev_parse_rules[i],
					      &short_name_len);
		if (!short_name)
			continue;

		/*
		 * in strict mode, all (except the matched one) rules
		 * must fail to resolve to a valid non-ambiguous ref
		 */
		if (strict)
			rules_to_fail = NUM_REV_PARSE_RULES;

		/*
		 * check if the short name resolves to a valid ref,
		 * but use only rules prior to the matched one
		 */
		for (j = 0; j < rules_to_fail; j++) {
			const char *rule = ref_rev_parse_rules[j];

			/* skip matched rule */
			if (i == j)
				continue;

			/*
			 * the short name is ambiguous, if it resolves
			 * (with this previous rule) to a valid ref
			 * read_ref() returns 0 on success
			 */
			strbuf_reset(&resolved_buf);
			strbuf_addf(&resolved_buf, rule,
				    cast_size_t_to_int(short_name_len),
				    short_name);
			if (refs_ref_exists(refs, resolved_buf.buf))
				break;
		}

		/*
		 * short name is non-ambiguous if all previous rules
		 * haven't resolved to a valid ref
		 */
		if (j == rules_to_fail) {
			strbuf_release(&resolved_buf);
			return xmemdupz(short_name, short_name_len);
		}
	}

	strbuf_release(&resolved_buf);
	return xstrdup(refname);
}

/**
 * Shorten the given refname to an unambiguous short name,
 * by removing the shortest prefix that causes the refname
 * to resolve to a valid ref using any of the rules prior
 * to the one that resolves to the provided refname.
 *
 * If strict is true, ensure all rules (except the one that
 * resolves to refname) do not resolve to a valid ref.
 *
 * Returns the shortened refname if non-ambiguous, otherwise
 * returns a copy of the original refname.
 */
char *shorten_unambiguous_ref(const char *refname, int strict)
{
	return refs_shorten_unambiguous_ref(get_main_ref_store(the_repository),
					    refname, strict);
}

/**
 * Parse configuration options related to hiding refs from output.
 *
 * @param var Config variable name
 * @param value Config variable value
 * @param section Config section name
 * @param hide_refs List of patterns for refs to hide
 */
int parse_hide_refs_config(const char *var, const char *value,
			   const char *section,
			   struct strvec *hide_refs)
{
	const char *key;
	if (!strcmp("transfer.hiderefs", var) ||
	    (!parse_config_key(var, section, NULL, NULL, &key) &&
	     !strcmp(key, "hiderefs"))) {
		char *ref;
		int len;

		if (!value)
			return config_error_nonbool(var);

		/* drop const to remove trailing '/' characters */
		ref = (char *)strvec_push(hide_refs, value);
		len = strlen(ref);
		while (len && ref[len - 1] == '/')
			ref[--len] = '\0';
	}
	return 0;
}

/**
 * Checks if a refname matches any patterns in the provided hide_refs list
 * indicating it should be hidden from output.
 *
 * @param refname The refname to check
 * @param refname_full The full refname to check
 * @param hide_refs The list of hidden ref patterns
 * @return 1 if the ref should be hidden, 0 otherwise
 */
int ref_is_hidden(const char *refname, const char *refname_full,
		  const struct strvec *hide_refs)
{
	int i;

	for (i = hide_refs->nr - 1; i >= 0; i--) {
		const char *match = hide_refs->v[i];
		const char *subject;
		int neg = 0;
		const char *p;

		if (*match == '!') {
			neg = 1;
			match++;
		}

		if (*match == '^') {
			subject = refname_full;
			match++;
		} else {
			subject = refname;
		}

		/* refname can be NULL when namespaces are used. */
		if (subject &&
		    skip_prefix(subject, match, &p) &&
		    (!*p || *p == '/'))
			return !neg;
	}
	return 0;
}

/**
 * Returns a pointer to the array of hidden refs patterns,
 * converted to exclude patterns suitable for passing to
 * other functions.
 *
 * @param hide_refs Array of hidden refs patterns.
 * @return Pointer to array of excludes.
 */
const char **hidden_refs_to_excludes(const struct strvec *hide_refs)
{
	const char **pattern;
	for (pattern = hide_refs->v; *pattern; pattern++) {
		/*
		 * We can't feed any excludes from hidden refs config
		 * sections, since later rules may override previous
		 * ones. For example, with rules "refs/foo" and
		 * "!refs/foo/bar", we should show "refs/foo/bar" (and
		 * everything underneath it), but the earlier exclusion
		 * would cause us to skip all of "refs/foo".  We
		 * likewise don't implement the namespace stripping
		 * required for '^' rules.
		 *
		 * Both are possible to do, but complicated, so avoid
		 * populating the jump list at all if we see either of
		 * these patterns.
		 */
		if (**pattern == '!' || **pattern == '^')
			return NULL;
	}
	return hide_refs->v;
}

/**
 * Find a refname that is a descendant of dirname.
 *
 * This will return the name of a ref that starts with dirname/
 * and is not excluded by the given string_list skip list. If no
 * qualifying ref exists, return NULL.
 */
const char *find_descendant_ref(const char *dirname,
				const struct string_list *extras,
				const struct string_list *skip)
{
	int pos;

	if (!extras)
		return NULL;

	/*
	 * Look at the place where dirname would be inserted into
	 * extras. If there is an entry at that position that starts
	 * with dirname (remember, dirname includes the trailing
	 * slash) and is not in skip, then we have a conflict.
	 */
	for (pos = string_list_find_insert_index(extras, dirname, 0);
	     pos < extras->nr; pos++) {
		const char *extra_refname = extras->items[pos].string;

		if (!starts_with(extra_refname, dirname))
			break;

		if (!skip || !string_list_has_string(skip, extra_refname))
			return extra_refname;
	}
	return NULL;
}

/**
 * Call the given callback fn for the HEAD reference.
 * @param refs the ref_store to get the HEAD ref from
 * @param fn the callback function to call
 * @param cb_data the data to pass to the callback function
 * @return 0 on success, non-zero callback return value on error
 */
int refs_head_ref(struct ref_store *refs, each_ref_fn fn, void *cb_data)
{
	struct object_id oid;
	int flag;

	if (refs_resolve_ref_unsafe(refs, "HEAD", RESOLVE_REF_READING,
				    &oid, &flag))
		return fn("HEAD", &oid, flag, cb_data);

	return 0;
}

/**
 * Call the given callback fn for the HEAD reference.
 *
 * @param fn the callback function
 * @param cb_data the data to pass to the callback function
 * @return 0 on success, non-zero callback return value on error
 */
int head_ref(each_ref_fn fn, void *cb_data)
{
	return refs_head_ref(get_main_ref_store(the_repository), fn, cb_data);
}

/**
 * Begin an iteration over references with the given prefix
 * from the specified ref_store.
 */
struct ref_iterator *refs_ref_iterator_begin(
		struct ref_store *refs,
		const char *prefix,
		const char **exclude_patterns,
		int trim,
		enum do_for_each_ref_flags flags)
{
	struct ref_iterator *iter;

	if (!(flags & DO_FOR_EACH_INCLUDE_BROKEN)) {
		static int ref_paranoia = -1;

		if (ref_paranoia < 0)
			ref_paranoia = git_env_bool("GIT_REF_PARANOIA", 1);
		if (ref_paranoia) {
			flags |= DO_FOR_EACH_INCLUDE_BROKEN;
			flags |= DO_FOR_EACH_OMIT_DANGLING_SYMREFS;
		}
	}

	iter = refs->be->iterator_begin(refs, prefix, exclude_patterns, flags);
	/*
	 * `iterator_begin()` already takes care of prefix, but we
	 * might need to do some trimming:
	 */
	if (trim)
		iter = prefix_ref_iterator_begin(iter, "", trim);

	/* Sanity check for subclasses: */
	if (!iter->ordered)
		BUG("reference iterator is not ordered");

	return iter;
}

/*
 * Call fn for each reference in the specified submodule for which the
 * refname begins with prefix. If trim is non-zero, then trim that
 * many characters off the beginning of each refname before passing
 * the refname to fn. flags can be DO_FOR_EACH_INCLUDE_BROKEN to
 * include broken references in the iteration. If fn ever returns a
 * non-zero value, stop the iteration and return that value;
 * otherwise, return 0.
 */
/**
 * Iterate over all references with the given prefix in the repository 'r',
 * invoking the callback function 'fn' for each reference.
 *
 * This is an internal helper function.
 */
static int do_for_each_repo_ref(struct repository *r, const char *prefix,
				each_repo_ref_fn fn, int trim, int flags,
				void *cb_data)
{
	struct ref_iterator *iter;
	struct ref_store *refs = get_main_ref_store(r);

	if (!refs)
		return 0;

	iter = refs_ref_iterator_begin(refs, prefix, NULL, trim, flags);

	return do_for_each_repo_ref_iterator(r, iter, fn, cb_data);
}

struct do_for_each_ref_help {
	each_ref_fn *fn;
	void *cb_data;
};

/**
 * Helper function called by do_for_each_repo_ref_iterator() to invoke the
 * callback function fn for each reference. Passes the reference name,
 * object ID, flags, and callback data to the callback.
 */
static int do_for_each_ref_helper(struct repository *r UNUSED,
				  const char *refname,
				  const struct object_id *oid,
				  int flags,
				  void *cb_data)
{
	struct do_for_each_ref_help *hp = cb_data;

	return hp->fn(refname, oid, flags, hp->cb_data);
}

/**
 * Iterate over all references with the given prefix in the given
 * reference store, invoking fn() for each reference.
 */
static int do_for_each_ref(struct ref_store *refs, const char *prefix,
			   const char **exclude_patterns,
			   each_ref_fn fn, int trim,
			   enum do_for_each_ref_flags flags, void *cb_data)
{
	struct ref_iterator *iter;
	struct do_for_each_ref_help hp = { fn, cb_data };

	if (!refs)
		return 0;

	iter = refs_ref_iterator_begin(refs, prefix, exclude_patterns, trim,
				       flags);

	return do_for_each_repo_ref_iterator(the_repository, iter,
					do_for_each_ref_helper, &hp);
}

/**
 * Iterate over all references in the given
 * reference store, invoking fn() for each reference.
 */
int refs_for_each_ref(struct ref_store *refs, each_ref_fn fn, void *cb_data)
{
	return do_for_each_ref(refs, "", NULL, fn, 0, 0, cb_data);
}

/**
 * Iterate over all references in the main reference store,
 * invoking fn() for each reference.
 *
 * @param fn Callback function to invoke for each reference.
 * @param cb_data Data to pass to the callback function.
 * @return 0 on success, non-zero on error.
 */
int for_each_ref(each_ref_fn fn, void *cb_data)
{
	return refs_for_each_ref(get_main_ref_store(the_repository), fn, cb_data);
}

/**
 * Iterate over all references with the given prefix in the given
 * reference store, invoking fn() for each.
 */
int refs_for_each_ref_in(struct ref_store *refs, const char *prefix,
			 each_ref_fn fn, void *cb_data)
{
	return do_for_each_ref(refs, prefix, NULL, fn, strlen(prefix), 0, cb_data);
}

/**
 * Iterate over all references with the given prefix in the main
 * reference store, invoking fn() for each.
 */
int for_each_ref_in(const char *prefix, each_ref_fn fn, void *cb_data)
{
	return refs_for_each_ref_in(get_main_ref_store(the_repository), prefix, fn, cb_data);
}

/**
 * Iterate over all references with the given prefix in the main
 * reference store, invoking fn() for each.
 *
 * This iterates over all references, including broken ones.
 */
int for_each_fullref_in(const char *prefix, each_ref_fn fn, void *cb_data)
{
	return do_for_each_ref(get_main_ref_store(the_repository),
			       prefix, NULL, fn, 0, 0, cb_data);
}

/**
 * Iterate over all references with the given prefix in the given
 * reference store, invoking fn() for each.
 *
 * This iterates over all references, including broken ones.
 */
int refs_for_each_fullref_in(struct ref_store *refs, const char *prefix,
			     const char **exclude_patterns,
			     each_ref_fn fn, void *cb_data)
{
	return do_for_each_ref(refs, prefix, exclude_patterns, fn, 0, 0, cb_data);
}

/**
 * Iterate over all replace references in the given repository.
 *
 * @param r repository
 * @param fn callback function to invoke for each replace reference
 * @param cb_data data to pass to callback function
 * @return 0 on success, non-zero on failure
 */
int for_each_replace_ref(struct repository *r, each_repo_ref_fn fn,
			 void *cb_data)
{
	const char *git_replace_ref_base = ref_namespace[NAMESPACE_REPLACE].ref;
	return do_for_each_repo_ref(r, git_replace_ref_base, fn,
				    strlen(git_replace_ref_base),
				    DO_FOR_EACH_INCLUDE_BROKEN, cb_data);
}

/**
 * Iterate over all references with the given prefix,
 * invoking fn() for each.
 *
 * exclude_patterns may be set to an array of glob patterns
 * to exclude some refs from the iteration.
 *
 * Returns 0 on success, non-zero on failure.
 */
int for_each_namespaced_ref(const char **exclude_patterns,
			    each_ref_fn fn, void *cb_data)
{
	struct strbuf buf = STRBUF_INIT;
	int ret;
	strbuf_addf(&buf, "%srefs/", get_git_namespace());
	ret = do_for_each_ref(get_main_ref_store(the_repository),
			      buf.buf, exclude_patterns, fn, 0, 0, cb_data);
	strbuf_release(&buf);
	return ret;
}

/**
 * Iterate over all raw references in the given reference store.
 *
 * @param refs reference store
 * @param fn callback function to invoke for each raw reference
 * @param cb_data data to pass to callback function
 * @return 0 on success, non-zero on failure
 */
int refs_for_each_rawref(struct ref_store *refs, each_ref_fn fn, void *cb_data)
{
	return do_for_each_ref(refs, "", NULL, fn, 0,
			       DO_FOR_EACH_INCLUDE_BROKEN, cb_data);
}

/**
 * Iterate over all references in the repository.
 *
 * @param fn callback function to invoke for each reference
 * @param cb_data data to pass to callback function
 * @return 0 on success, non-zero on failure
 */
int for_each_rawref(each_ref_fn fn, void *cb_data)
{
	return refs_for_each_rawref(get_main_ref_store(the_repository), fn, cb_data);
}

/**
 * Compare two string pointers lexicographically for qsort.
 *
 * This is a helper function for string sorting using qsort.
 * It receives two const void* pointers which are cast to string pointers.
 * Returns negative/0/positive integer depending on the comparison result,
 * for use as a qsort comparator.
 */
static int qsort_strcmp(const void *va, const void *vb)
{
	const char *a = *(const char **)va;
	const char *b = *(const char **)vb;

	return strcmp(a, b);
}

/**
 * Recursively finds the longest common prefixes in the given array of
 * pattern strings and appends them to the given string_list 'out'.
 *
 * @param out the string_list to append found prefixes to
 * @param prefix the current prefix being examined
 * @param patterns array of pattern strings
 * @param nr number of elements in patterns array
 */
static void find_longest_prefixes_1(struct string_list *out,
				  struct strbuf *prefix,
				  const char **patterns, size_t nr)
{
	size_t i;

	for (i = 0; i < nr; i++) {
		char c = patterns[i][prefix->len];
		if (!c || is_glob_special(c)) {
			string_list_append(out, prefix->buf);
			return;
		}
	}

	i = 0;
	while (i < nr) {
		size_t end;

		/*
		* Set "end" to the index of the element _after_ the last one
		* in our group.
		*/
		for (end = i + 1; end < nr; end++) {
			if (patterns[i][prefix->len] != patterns[end][prefix->len])
				break;
		}

		strbuf_addch(prefix, patterns[i][prefix->len]);
		find_longest_prefixes_1(out, prefix, patterns + i, end - i);
		strbuf_setlen(prefix, prefix->len - 1);

		i = end;
	}
}

/**
 * Find the longest common prefixes in the given array of pattern
 * strings and append them to the given string_list 'out'.
 *
 * The patterns array is sorted before processing.
 */
static void find_longest_prefixes(struct string_list *out,
				  const char **patterns)
{
	struct strvec sorted = STRVEC_INIT;
	struct strbuf prefix = STRBUF_INIT;

	strvec_pushv(&sorted, patterns);
	QSORT(sorted.v, sorted.nr, qsort_strcmp);

	find_longest_prefixes_1(out, &prefix, sorted.v, sorted.nr);

	strvec_clear(&sorted);
	strbuf_release(&prefix);
}

/**
 * Iterate over all references in the given `ref_store` whose names start
 * with one of the provided prefix strings in `patterns`.
 *
 * Exclude any references matching the given `exclude_patterns`.
 *
 * For each reference, call the callback function `fn` with the reference
 * name, oid, type, flags and the callback data pointer `cb_data`.
 *
 * If the callback returns a non-zero value, stop the iteration and
 * return the value. Returns 0 otherwise.
 */
int refs_for_each_fullref_in_prefixes(struct ref_store *ref_store,
				      const char *namespace,
				      const char **patterns,
				      const char **exclude_patterns,
				      each_ref_fn fn, void *cb_data)
{
	struct string_list prefixes = STRING_LIST_INIT_DUP;
	struct string_list_item *prefix;
	struct strbuf buf = STRBUF_INIT;
	int ret = 0, namespace_len;

	find_longest_prefixes(&prefixes, patterns);

	if (namespace)
		strbuf_addstr(&buf, namespace);
	namespace_len = buf.len;

	for_each_string_list_item(prefix, &prefixes) {
		strbuf_addstr(&buf, prefix->string);
		ret = refs_for_each_fullref_in(ref_store, buf.buf,
					       exclude_patterns, fn, cb_data);
		if (ret)
			break;
		strbuf_setlen(&buf, namespace_len);
	}

	string_list_clear(&prefixes, 0);
	strbuf_release(&buf);
	return ret;
}

/**
 * Read the reference object for special references like
 * FETCH_HEAD and MERGE_HEAD from the given ref_store.
 */
static int refs_read_special_head(struct ref_store *ref_store,
				  const char *refname, struct object_id *oid,
				  struct strbuf *referent, unsigned int *type,
				  int *failure_errno)
{
	struct strbuf full_path = STRBUF_INIT;
	struct strbuf content = STRBUF_INIT;
	int result = -1;
	strbuf_addf(&full_path, "%s/%s", ref_store->gitdir, refname);

	if (strbuf_read_file(&content, full_path.buf, 0) < 0)
		goto done;

	result = parse_loose_ref_contents(content.buf, oid, referent, type,
					  failure_errno);

done:
	strbuf_release(&full_path);
	strbuf_release(&content);
	return result;
}

/**
 * Read the raw reference for the given refname from the ref_store.
 * @param ref_store the ref_store to read from
 * @param refname the name of the reference to read
 */
int refs_read_raw_ref(struct ref_store *ref_store, const char *refname,
		      struct object_id *oid, struct strbuf *referent,
		      unsigned int *type, int *failure_errno)
{
	assert(failure_errno);
	if (!strcmp(refname, "FETCH_HEAD") || !strcmp(refname, "MERGE_HEAD")) {
		return refs_read_special_head(ref_store, refname, oid, referent,
					      type, failure_errno);
	}

	return ref_store->be->read_raw_ref(ref_store, refname, oid, referent,
					   type, failure_errno);
}

/**
 * Read the symbolic ref for the given refname from the ref_store and store
 * it in the referent strbuf. Return 0 on success.
 */
int refs_read_symbolic_ref(struct ref_store *ref_store, const char *refname,
			   struct strbuf *referent)
{
	return ref_store->be->read_symbolic_ref(ref_store, refname, referent);
}

/**
 * Resolve a reference name in an unsafe/unvalidated way, recursively following
 * symbolic references until a concrete reference is found or the recursion
 * limit is reached.
 *
 * @param refs the ref_store to resolve from
 * @param refname the reference name to resolve
 */
const char *refs_resolve_ref_unsafe(struct ref_store *refs,
				    const char *refname,
				    int resolve_flags,
				    struct object_id *oid,
				    int *flags)
{
	static struct strbuf sb_refname = STRBUF_INIT;
	struct object_id unused_oid;
	int unused_flags;
	int symref_count;

	if (!oid)
		oid = &unused_oid;
	if (!flags)
		flags = &unused_flags;

	*flags = 0;

	if (check_refname_format(refname, REFNAME_ALLOW_ONELEVEL)) {
		if (!(resolve_flags & RESOLVE_REF_ALLOW_BAD_NAME) ||
		    !refname_is_safe(refname))
			return NULL;

		/*
		 * repo_dwim_ref() uses REF_ISBROKEN to distinguish between
		 * missing refs and refs that were present but invalid,
		 * to complain about the latter to stderr.
		 *
		 * We don't know whether the ref exists, so don't set
		 * REF_ISBROKEN yet.
		 */
		*flags |= REF_BAD_NAME;
	}

	for (symref_count = 0; symref_count < SYMREF_MAXDEPTH; symref_count++) {
		unsigned int read_flags = 0;
		int failure_errno;

		if (refs_read_raw_ref(refs, refname, oid, &sb_refname,
				      &read_flags, &failure_errno)) {
			*flags |= read_flags;

			/* In reading mode, refs must eventually resolve */
			if (resolve_flags & RESOLVE_REF_READING)
				return NULL;

			/*
			 * Otherwise a missing ref is OK. But the files backend
			 * may show errors besides ENOENT if there are
			 * similarly-named refs.
			 */
			if (failure_errno != ENOENT &&
			    failure_errno != EISDIR &&
			    failure_errno != ENOTDIR)
				return NULL;

			oidclr(oid);
			if (*flags & REF_BAD_NAME)
				*flags |= REF_ISBROKEN;
			return refname;
		}

		*flags |= read_flags;

		if (!(read_flags & REF_ISSYMREF)) {
			if (*flags & REF_BAD_NAME) {
				oidclr(oid);
				*flags |= REF_ISBROKEN;
			}
			return refname;
		}

		refname = sb_refname.buf;
		if (resolve_flags & RESOLVE_REF_NO_RECURSE) {
			oidclr(oid);
			return refname;
		}
		if (check_refname_format(refname, REFNAME_ALLOW_ONELEVEL)) {
			if (!(resolve_flags & RESOLVE_REF_ALLOW_BAD_NAME) ||
			    !refname_is_safe(refname))
				return NULL;

			*flags |= REF_ISBROKEN | REF_BAD_NAME;
		}
	}

	return NULL;
}

/* backend functions */
/**
 * Initialize the reference database for the main reference store.
 *
 * @param err strbuf to write error messages to on failure
 * @return 0 on success, non-zero on failure
 */
int refs_init_db(struct strbuf *err)
{
	struct ref_store *refs = get_main_ref_store(the_repository);

	return refs->be->init_db(refs, err);
}

/**
 * Resolve a ref name to a SHA-1 object id in an unsafe manner.
 *
 * This function resolves a ref name to a SHA-1 object id without
 * checking if the ref name is safe or valid. The caller is responsible
 * for performing those checks before calling this function.
 *
 * @param refname Name of ref to resolve.
 * @param resolve_flags Flags that control the resolve behavior.
 * @param oid Pointer to store resolved object ID.
 * @param flags Pointer to store resolve flags.
 */
const char *resolve_ref_unsafe(const char *refname, int resolve_flags,
			       struct object_id *oid, int *flags)
{
	return refs_resolve_ref_unsafe(get_main_ref_store(the_repository), refname,
				       resolve_flags, oid, flags);
}

/**
 * Resolve a symbolic ref from the submodule into a SHA-1 object id.
 *
 * @param submodule Path to submodule.
 * @param refname Name of symbolic ref to resolve.
 * @param oid Pointer to store resolved object ID.
 * @return 0 on success, non-zero on failure.
 */
int resolve_gitlink_ref(const char *submodule, const char *refname,
			struct object_id *oid)
{
	struct ref_store *refs;
	int flags;

	refs = get_submodule_ref_store(submodule);

	if (!refs)
		return -1;

	if (!refs_resolve_ref_unsafe(refs, refname, 0, oid, &flags) ||
	    is_null_oid(oid))
		return -1;
	return 0;
}

struct ref_store_hash_entry
{
	struct hashmap_entry ent;

	struct ref_store *refs;

	/* NUL-terminated identifier of the ref store: */
	char name[FLEX_ARRAY];
};

/**
 * Compare function for the ref_store hashmaps. Compares two
 * ref_store_hash_entry structs by name.
 */
static int ref_store_hash_cmp(const void *cmp_data UNUSED,
			      const struct hashmap_entry *eptr,
			      const struct hashmap_entry *entry_or_key,
			      const void *keydata)
{
	const struct ref_store_hash_entry *e1, *e2;
	const char *name;

	e1 = container_of(eptr, const struct ref_store_hash_entry, ent);
	e2 = container_of(entry_or_key, const struct ref_store_hash_entry, ent);
	name = keydata ? keydata : e2->name;

	return strcmp(e1->name, name);
}

/**
 * Allocate and initialize a new ref_store_hash_entry struct.
 * This struct contains a ref_store instance and metadata to
 * store it in a hashmap by name.
 */
static struct ref_store_hash_entry *
alloc_ref_store_hash_entry(
		const char *name, struct ref_store *refs)
{
	struct ref_store_hash_entry *entry;

	FLEX_ALLOC_STR(entry, name, name);
	hashmap_entry_init(&entry->ent, strhash(name));
	entry->refs = refs;
	return entry;
}

/* A hashmap of ref_stores, stored by submodule name: */
static struct hashmap submodule_ref_stores;

/* A hashmap of ref_stores, stored by worktree id: */
static struct hashmap worktree_ref_stores;

/*
 * Look up a ref store by name. If that ref_store hasn't been
 * registered yet, return NULL.
 */
/**
 * Lookup a ref_store instance in the given hashmap by name.
 *
 * @param map hashmap to search
 * @param name name of the ref_store to find
 * @return the ref_store instance, or NULL if not found
 */
static struct ref_store *lookup_ref_store_map(struct hashmap *map,
					      const char *name)
{
	struct ref_store_hash_entry *entry;
	unsigned int hash;

	if (!map->tablesize)
		/* It's initialized on demand in register_ref_store(). */
		return NULL;

	hash = strhash(name);
	entry = hashmap_get_entry_from_hash(map, hash, name,
					struct ref_store_hash_entry, ent);
	return entry ? entry->refs : NULL;
}

/*
 * Create, record, and return a ref_store instance for the specified
 * gitdir.
 */
/**
 * Initialize a ref_store instance for the specified git directory.
 *
 * @param repo the repository structure
 * @param gitdir path to the git directory
 * @return the initialized ref_store instance
 */
static struct ref_store *ref_store_init(struct repository *repo,
					const char *gitdir,
					unsigned int flags)
{
	const char *be_name = "files";
	struct ref_storage_be *be = find_ref_storage_backend(be_name);
	struct ref_store *refs;

	if (!be)
		BUG("reference backend %s is unknown", be_name);

	refs = be->init(repo, gitdir, flags);
	return refs;
}

/**
 * Get the main ref store for the given repository.
 *
 * @param r repository
 * @return the main ref store for the repository
 */
struct ref_store *get_main_ref_store(struct repository *r)
{
	if (r->refs_private)
		return r->refs_private;

	if (!r->gitdir)
		BUG("attempting to get main_ref_store outside of repository");

	r->refs_private = ref_store_init(r, r->gitdir, REF_STORE_ALL_CAPS);
	r->refs_private = maybe_debug_wrap_ref_store(r->gitdir, r->refs_private);
	return r->refs_private;
}

/*
 * Associate a ref store with a name. It is a fatal error to call this
 * function twice for the same name.
 */
/**
 * Register a ref store in the provided hashmap.
 *
 * @param map Hashmap to register ref store in.
 *
 */
static void register_ref_store_map(struct hashmap *map,
				   const char *type,
				   struct ref_store *refs,
				   const char *name)
{
	struct ref_store_hash_entry *entry;

	if (!map->tablesize)
		hashmap_init(map, ref_store_hash_cmp, NULL, 0);

	entry = alloc_ref_store_hash_entry(name, refs);
	if (hashmap_put(map, &entry->ent))
		BUG("%s ref_store '%s' initialized twice", type, name);
}

/**
 * Get the ref_store for the specified submodule.
 *
 * @param submodule Path to the submodule.
 * @return Pointer to the ref_store for the submodule, or NULL if not found.
 */
struct ref_store *get_submodule_ref_store(const char *submodule)
{
	struct strbuf submodule_sb = STRBUF_INIT;
	struct ref_store *refs;
	char *to_free = NULL;
	size_t len;
	struct repository *subrepo;

	if (!submodule)
		return NULL;

	len = strlen(submodule);
	while (len && is_dir_sep(submodule[len - 1]))
		len--;
	if (!len)
		return NULL;

	if (submodule[len])
		/* We need to strip off one or more trailing slashes */
		submodule = to_free = xmemdupz(submodule, len);

	refs = lookup_ref_store_map(&submodule_ref_stores, submodule);
	if (refs)
		goto done;

	strbuf_addstr(&submodule_sb, submodule);
	if (!is_nonbare_repository_dir(&submodule_sb))
		goto done;

	if (submodule_to_gitdir(&submodule_sb, submodule))
		goto done;

	subrepo = xmalloc(sizeof(*subrepo));
	/*
	 * NEEDSWORK: Make get_submodule_ref_store() work with arbitrary
	 * superprojects other than the_repository. This probably should be
	 * done by making it take a struct repository * parameter instead of a
	 * submodule path.
	 */
	if (repo_submodule_init(subrepo, the_repository, submodule,
				null_oid())) {
		free(subrepo);
		goto done;
	}
	refs = ref_store_init(subrepo, submodule_sb.buf,
			      REF_STORE_READ | REF_STORE_ODB);
	register_ref_store_map(&submodule_ref_stores, "submodule",
			       refs, submodule);

done:
	strbuf_release(&submodule_sb);
	free(to_free);

	return refs;
}

/**
 * Get the ref_store for the given worktree.
 *
 * @param wt Pointer to the worktree
 * @return Pointer to the ref_store for the worktree, or NULL if not found
 */
struct ref_store *get_worktree_ref_store(const struct worktree *wt)
{
	struct ref_store *refs;
	const char *id;

	if (wt->is_current)
		return get_main_ref_store(the_repository);

	id = wt->id ? wt->id : "/";
	refs = lookup_ref_store_map(&worktree_ref_stores, id);
	if (refs)
		return refs;

	if (wt->id)
		refs = ref_store_init(the_repository,
				      git_common_path("worktrees/%s", wt->id),
				      REF_STORE_ALL_CAPS);
	else
		refs = ref_store_init(the_repository,
				      get_git_common_dir(),
				      REF_STORE_ALL_CAPS);

	if (refs)
		register_ref_store_map(&worktree_ref_stores, "worktree",
				       refs, id);
	return refs;
}

/**
 * Initialize a ref_store struct.
 *
 * @param refs the ref_store to initialize
 * @param repo the repository this ref_store is associated with
 */
void base_ref_store_init(struct ref_store *refs, struct repository *repo,
			 const char *path, const struct ref_storage_be *be)
{
	refs->be = be;
	refs->repo = repo;
	refs->gitdir = xstrdup(path);
}

/* backend functions */
/**
 * Pack all loose refs in the specified ref_store into packed-refs
 * file.
 *
 * @param refs the ref_store containing loose refs to pack
 * @param opts options for packing refs
 * @return 0 on success, non-zero on failure
 */
int refs_pack_refs(struct ref_store *refs, struct pack_refs_opts *opts)
{
	return refs->be->pack_refs(refs, opts);
}

/**
 * Peels the given object ID by dereferencing it recursively, writing the
 * resulting peeled object ID into peeled.
 * Returns 0 on success. Returns -1 if the object could not be peeled.
 */
int peel_iterated_oid(const struct object_id *base, struct object_id *peeled)
{
	if (current_ref_iter &&
	    (current_ref_iter->oid == base ||
	     oideq(current_ref_iter->oid, base)))
		return ref_iterator_peel(current_ref_iter, peeled);

	return peel_object(base, peeled) ? -1 : 0;
}

/**
 * Create a symbolic ref in the given ref_store.
 *
 * @param refs the ref_store to create the symbolic ref in
 * @param ref_target Target ref to create
 * @param refs_heads_master Ref to point ref_target to
 * @param logmsg Log message for reflog
 * @return 0 on success, non-zero on failure
 */
int refs_create_symref(struct ref_store *refs,
		       const char *ref_target,
		       const char *refs_heads_master,
		       const char *logmsg)
{
	char *msg;
	int retval;

	msg = normalize_reflog_message(logmsg);
	retval = refs->be->create_symref(refs, ref_target, refs_heads_master,
					 msg);
	free(msg);
	return retval;
}

/**
 * Create a symbolic ref.
 *
 * Creates a symbolic ref from ref_target to refs_heads_master.
 *
 * @param ref_target Target ref to create
 * @param refs_heads_master Ref to point ref_target to
 */
int create_symref(const char *ref_target, const char *refs_heads_master,
		  const char *logmsg)
{
	return refs_create_symref(get_main_ref_store(the_repository), ref_target,
				  refs_heads_master, logmsg);
}

/**
 * Check if there are duplicate refnames in the given string_list, which is
 * assumed to be sorted. Returns 0 if no duplicates, non-zero otherwise.
 */
int ref_update_reject_duplicates(struct string_list *refnames,
				 struct strbuf *err)
{
	size_t i, n = refnames->nr;

	assert(err);

	for (i = 1; i < n; i++) {
		int cmp = strcmp(refnames->items[i - 1].string,
				 refnames->items[i].string);

		if (!cmp) {
			strbuf_addf(err,
				    _("multiple updates for ref '%s' not allowed"),
				    refnames->items[i].string);
			return 1;
		} else if (cmp > 0) {
			BUG("ref_update_reject_duplicates() received unsorted list");
		}
	}
	return 0;
}

/**
 * Run the reference transaction hook.
 *
 * @param transaction the reference transaction being performed
 * @param state the state of the transaction (e.g. "pre" or "post")
 */
static int run_transaction_hook(struct ref_transaction *transaction,
				const char *state)
{
	struct child_process proc = CHILD_PROCESS_INIT;
	struct strbuf buf = STRBUF_INIT;
	const char *hook;
	int ret = 0, i;

	hook = find_hook("reference-transaction");
	if (!hook)
		return ret;

	strvec_pushl(&proc.args, hook, state, NULL);
	proc.in = -1;
	proc.stdout_to_stderr = 1;
	proc.trace2_hook_name = "reference-transaction";

	ret = start_command(&proc);
	if (ret)
		return ret;

	sigchain_push(SIGPIPE, SIG_IGN);

	for (i = 0; i < transaction->nr; i++) {
		struct ref_update *update = transaction->updates[i];

		strbuf_reset(&buf);
		strbuf_addf(&buf, "%s %s %s\n",
			    oid_to_hex(&update->old_oid),
			    oid_to_hex(&update->new_oid),
			    update->refname);

		if (write_in_full(proc.in, buf.buf, buf.len) < 0) {
			if (errno != EPIPE) {
				/* Don't leak errno outside this API */
				errno = 0;
				ret = -1;
			}
			break;
		}
	}

	close(proc.in);
	sigchain_pop(SIGPIPE);
	strbuf_release(&buf);

	ret |= finish_command(&proc);
	return ret;
}

/**
 * Prepare a reference transaction for commit. Checks that the
 * transaction is valid and initializes the underlying backend
 * transaction.
 */
int ref_transaction_prepare(struct ref_transaction *transaction,
			    struct strbuf *err)
{
	struct ref_store *refs = transaction->ref_store;
	int ret;

	switch (transaction->state) {
	case REF_TRANSACTION_OPEN:
		/* Good. */
		break;
	case REF_TRANSACTION_PREPARED:
		BUG("prepare called twice on reference transaction");
		break;
	case REF_TRANSACTION_CLOSED:
		BUG("prepare called on a closed reference transaction");
		break;
	default:
		BUG("unexpected reference transaction state");
		break;
	}

	if (refs->repo->objects->odb->disable_ref_updates) {
		strbuf_addstr(err,
			      _("ref updates forbidden inside quarantine environment"));
		return -1;
	}

	ret = refs->be->transaction_prepare(refs, transaction, err);
	if (ret)
		return ret;

	ret = run_transaction_hook(transaction, "prepared");
	if (ret) {
		ref_transaction_abort(transaction, err);
		die(_("ref updates aborted by hook"));
	}

	return 0;
}

/**
 * Abort a reference transaction.
 *
 * Aborts the changes queued in the given reference transaction.
 * The transaction must be prepared first before calling this function.
 */
int ref_transaction_abort(struct ref_transaction *transaction,
			  struct strbuf *err)
{
	struct ref_store *refs = transaction->ref_store;
	int ret = 0;

	switch (transaction->state) {
	case REF_TRANSACTION_OPEN:
		/* No need to abort explicitly. */
		break;
	case REF_TRANSACTION_PREPARED:
		ret = refs->be->transaction_abort(refs, transaction, err);
		break;
	case REF_TRANSACTION_CLOSED:
		BUG("abort called on a closed reference transaction");
		break;
	default:
		BUG("unexpected reference transaction state");
		break;
	}

	run_transaction_hook(transaction, "aborted");

	ref_transaction_free(transaction);
	return ret;
}

/**
 * Commit a reference transaction.
 *
 * Commits the changes queued in the given reference transaction.
 * The transaction must be prepared first before calling this function.
 *
 * @param transaction the reference transaction to commit
 * @param err a strbuf for reporting errors
 * @return 0 on success, negative error code on failure
 */
int ref_transaction_commit(struct ref_transaction *transaction,
			   struct strbuf *err)
{
	struct ref_store *refs = transaction->ref_store;
	int ret;

	switch (transaction->state) {
	case REF_TRANSACTION_OPEN:
		/* Need to prepare first. */
		ret = ref_transaction_prepare(transaction, err);
		if (ret)
			return ret;
		break;
	case REF_TRANSACTION_PREPARED:
		/* Fall through to finish. */
		break;
	case REF_TRANSACTION_CLOSED:
		BUG("commit called on a closed reference transaction");
		break;
	default:
		BUG("unexpected reference transaction state");
		break;
	}

	ret = refs->be->transaction_finish(refs, transaction, err);
	if (!ret)
		run_transaction_hook(transaction, "committed");
	return ret;
}

/**
 * refs_verify_refname_available - Check if a refname is available to use
 * @refs: Pointer to the ref_store to check against
 *
 * Verify that a refname is valid and available for use. This checks
 * that the refname contains valid characters and does not conflict
 * with an existing ref.
 *
 * Returns 0 on success, negative error code on failure.
 */
int refs_verify_refname_available(struct ref_store *refs,
				  const char *refname,
				  const struct string_list *extras,
				  const struct string_list *skip,
				  struct strbuf *err)
{
	const char *slash;
	const char *extra_refname;
	struct strbuf dirname = STRBUF_INIT;
	struct strbuf referent = STRBUF_INIT;
	struct object_id oid;
	unsigned int type;
	struct ref_iterator *iter;
	int ok;
	int ret = -1;

	/*
	 * For the sake of comments in this function, suppose that
	 * refname is "refs/foo/bar".
	 */

	assert(err);

	strbuf_grow(&dirname, strlen(refname) + 1);
	for (slash = strchr(refname, '/'); slash; slash = strchr(slash + 1, '/')) {
		/*
		 * Just saying "Is a directory" when we e.g. can't
		 * lock some multi-level ref isn't very informative,
		 * the user won't be told *what* is a directory, so
		 * let's not use strerror() below.
		 */
		int ignore_errno;
		/* Expand dirname to the new prefix, not including the trailing slash: */
		strbuf_add(&dirname, refname + dirname.len, slash - refname - dirname.len);

		/*
		 * We are still at a leading dir of the refname (e.g.,
		 * "refs/foo"; if there is a reference with that name,
		 * it is a conflict, *unless* it is in skip.
		 */
		if (skip && string_list_has_string(skip, dirname.buf))
			continue;

		if (!refs_read_raw_ref(refs, dirname.buf, &oid, &referent,
				       &type, &ignore_errno)) {
			strbuf_addf(err, _("'%s' exists; cannot create '%s'"),
				    dirname.buf, refname);
			goto cleanup;
		}

		if (extras && string_list_has_string(extras, dirname.buf)) {
			strbuf_addf(err, _("cannot process '%s' and '%s' at the same time"),
				    refname, dirname.buf);
			goto cleanup;
		}
	}

	/*
	 * We are at the leaf of our refname (e.g., "refs/foo/bar").
	 * There is no point in searching for a reference with that
	 * name, because a refname isn't considered to conflict with
	 * itself. But we still need to check for references whose
	 * names are in the "refs/foo/bar/" namespace, because they
	 * *do* conflict.
	 */
	strbuf_addstr(&dirname, refname + dirname.len);
	strbuf_addch(&dirname, '/');

	iter = refs_ref_iterator_begin(refs, dirname.buf, NULL, 0,
				       DO_FOR_EACH_INCLUDE_BROKEN);
	while ((ok = ref_iterator_advance(iter)) == ITER_OK) {
		if (skip &&
		    string_list_has_string(skip, iter->refname))
			continue;

		strbuf_addf(err, _("'%s' exists; cannot create '%s'"),
			    iter->refname, refname);
		ref_iterator_abort(iter);
		goto cleanup;
	}

	if (ok != ITER_DONE)
		BUG("error while iterating over references");

	extra_refname = find_descendant_ref(dirname.buf, extras, skip);
	if (extra_refname)
		strbuf_addf(err, _("cannot process '%s' and '%s' at the same time"),
			    refname, extra_refname);
	else
		ret = 0;

cleanup:
	strbuf_release(&referent);
	strbuf_release(&dirname);
	return ret;
}

/**
 * Iterate over all reflog entries.
 *
 * @param refs the ref_store to iterate over
 * @param fn callback function to invoke for each reflog entry
 * @param cb_data extra data to pass to the callback function
 */
int refs_for_each_reflog(struct ref_store *refs, each_ref_fn fn, void *cb_data)
{
	struct ref_iterator *iter;
	struct do_for_each_ref_help hp = { fn, cb_data };

	iter = refs->be->reflog_iterator_begin(refs);

	return do_for_each_repo_ref_iterator(the_repository, iter,
					     do_for_each_ref_helper, &hp);
}

/**
 * Iterate over all reflog entries.
 *
 * @param fn callback function to invoke for each reflog entry
 * @param cb_data extra data to pass to the callback function
 */
int for_each_reflog(each_ref_fn fn, void *cb_data)
{
	return refs_for_each_reflog(get_main_ref_store(the_repository), fn, cb_data);
}

/**
 * Iterate over all reflog entries for the given ref in reverse order.
 *
 */
int refs_for_each_reflog_ent_reverse(struct ref_store *refs,
				     const char *refname,
				     each_reflog_ent_fn fn,
				     void *cb_data)
{
	return refs->be->for_each_reflog_ent_reverse(refs, refname,
						     fn, cb_data);
}

/**
 * Iterate over all reflog entries for the given ref in reverse order.
 *
 * @param refname name of the ref whose reflog should be iterated
 * @param fn callback function to invoke for each reflog entry
 * @param cb_data extra data to pass to the callback function
 * @return 0 on success, non-zero callback return value on error
 */
int for_each_reflog_ent_reverse(const char *refname, each_reflog_ent_fn fn,
				void *cb_data)
{
	return refs_for_each_reflog_ent_reverse(get_main_ref_store(the_repository),
						refname, fn, cb_data);
}

/**
 * Iterate over all reflog entries for the given ref.
 *
 * @param refs the ref_store to iterate over
 * @param refname name of the ref whose reflog should be iterated
 * @param fn callback function to invoke for each reflog entry
 */
int refs_for_each_reflog_ent(struct ref_store *refs, const char *refname,
			     each_reflog_ent_fn fn, void *cb_data)
{
	return refs->be->for_each_reflog_ent(refs, refname, fn, cb_data);
}

/**
 * Iterate over all reflog entries for the given ref.
 *
 * @param refname name of the ref whose reflog should be iterated
 * @param fn callback function to invoke for each reflog entry
 * @param cb_data extra data to pass to the callback function
 * @return 0 on success, non-zero callback return value on error
 */
int for_each_reflog_ent(const char *refname, each_reflog_ent_fn fn,
			void *cb_data)
{
	return refs_for_each_reflog_ent(get_main_ref_store(the_repository), refname,
					fn, cb_data);
}

/**
 * Checks if a reflog exists for the given refname.
 *
 * @param refs the ref_store to check
 * @param refname name of the ref to check for a reflog
 * @return 0 if a reflog exists, non-zero otherwise
 */
int refs_reflog_exists(struct ref_store *refs, const char *refname)
{
	return refs->be->reflog_exists(refs, refname);
}

/**
 * Checks if a reflog exists for the given refname.
 *
 * @param refname name of the ref to check for a reflog
 * @return 0 if a reflog exists, non-zero otherwise
 */
int reflog_exists(const char *refname)
{
	return refs_reflog_exists(get_main_ref_store(the_repository), refname);
}

/**
 * Creates a reflog for the given refname if it does not already exist.
 * @param refs the ref_store to create the reflog in
 * @param refname name of the ref whose reflog should be created
 */
int refs_create_reflog(struct ref_store *refs, const char *refname,
		       struct strbuf *err)
{
	return refs->be->create_reflog(refs, refname, err);
}

/**
 * Creates a reflog for the given refname if it does not already exist.
 *
 * @param refname name of the ref whose reflog should be created
 * @param err strbuf to write an error message to if creating fails
 * @return 0 on success, non-zero on failure
 */
int safe_create_reflog(const char *refname, struct strbuf *err)
{
	return refs_create_reflog(get_main_ref_store(the_repository), refname,
				  err);
}

/**
 * Deletes the reflog for the given refname.
 *
 * @param refs the ref_store containing the reflog
 * @param refname name of the ref whose reflog should be deleted
 * @return 0 on success, non-zero on failure
 */
int refs_delete_reflog(struct ref_store *refs, const char *refname)
{
	return refs->be->delete_reflog(refs, refname);
}

/**
 * Deletes the reflog for the given refname.
 *
 * @param refname name of the ref whose reflog should be deleted
 * @return 0 on success, non-zero on failure
 */
int delete_reflog(const char *refname)
{
	return refs_delete_reflog(get_main_ref_store(the_repository), refname);
}

/**
 * Expires reflog entries older than the specified expiry time.
 * refs: the ref_store containing the reflog
 *
 */
int refs_reflog_expire(struct ref_store *refs,
		       const char *refname,
		       unsigned int flags,
		       reflog_expiry_prepare_fn prepare_fn,
		       reflog_expiry_should_prune_fn should_prune_fn,
		       reflog_expiry_cleanup_fn cleanup_fn,
		       void *policy_cb_data)
{
	return refs->be->reflog_expire(refs, refname, flags,
				       prepare_fn, should_prune_fn,
				       cleanup_fn, policy_cb_data);
}

/**
 * Expires reflog entries older than the specified expiry time.
 *
 * @param refname name of the ref whose reflog should be expired
 * @param expire_at timestamp specifying cutoff time for expiring entries
 * @param flags flags affecting expiry behavior
 * @return 0 on success, non-zero on failure
 */
int reflog_expire(const char *refname,
		  unsigned int flags,
		  reflog_expiry_prepare_fn prepare_fn,
		  reflog_expiry_should_prune_fn should_prune_fn,
		  reflog_expiry_cleanup_fn cleanup_fn,
		  void *policy_cb_data)
{
	return refs_reflog_expire(get_main_ref_store(the_repository),
				  refname, flags,
				  prepare_fn, should_prune_fn,
				  cleanup_fn, policy_cb_data);
}

/**
 * Commit the specified ref transaction.
 *
 * This commits the changes queued in the transaction. The ref transaction
 * must represent the initial commit of a new ref.
 *
 * @param transaction the ref transaction to commit
 * @param err returns error details if commit fails
 * @return 0 on success, non-zero on failure
 */
int initial_ref_transaction_commit(struct ref_transaction *transaction,
				   struct strbuf *err)
{
	struct ref_store *refs = transaction->ref_store;

	return refs->be->initial_transaction_commit(refs, transaction, err);
}

/**
 * Iterate over all queued updates in the given ref transaction,
 * invoking the callback function for each.
 *
 * @param transaction the ref transaction to iterate over
 * @param cb callback function to invoke for each queued update
 * @param cb_data extra data to pass to the callback function
 */
void ref_transaction_for_each_queued_update(
	struct ref_transaction *transaction,
					    ref_transaction_for_each_queued_update_fn cb,
					    void *cb_data)
{
	int i;

	for (i = 0; i < transaction->nr; i++) {
		struct ref_update *update = transaction->updates[i];

		cb(update->refname,
		   (update->flags & REF_HAVE_OLD) ? &update->old_oid : NULL,
		   (update->flags & REF_HAVE_NEW) ? &update->new_oid : NULL,
		   cb_data);
	}
}

/**
 * Delete existing refs from the given ref_store.
 *
 * @param refs the ref_store containing the refs to delete
 * @param logmsg Log message to use for the reflog entry
 */
int refs_delete_refs(struct ref_store *refs, const char *logmsg,
		     struct string_list *refnames, unsigned int flags)
{
	char *msg;
	int retval;

	msg = normalize_reflog_message(logmsg);
	retval = refs->be->delete_refs(refs, msg, refnames, flags);
	free(msg);
	return retval;
}

/**
 * Delete existing refs from the repository.
 *
 * @param msg Log message.
 * @param refnames List of ref names to delete.
 * @param flags Bit flags that control delete_refs() behavior.
 * @return 0 on success, non-zero on failure.
 */
int delete_refs(const char *msg, struct string_list *refnames,
		unsigned int flags)
{
	return refs_delete_refs(get_main_ref_store(the_repository), msg, refnames, flags);
}

/**
 * Rename an existing ref stored in the given ref_store.
 *
 * @param refs the ref_store containing the ref to rename
 * @param oldref existing name of the ref to rename
 * @param newref new name to rename the ref to
 */
int refs_rename_ref(struct ref_store *refs, const char *oldref,
		    const char *newref, const char *logmsg)
{
	char *msg;
	int retval;

	msg = normalize_reflog_message(logmsg);
	retval = refs->be->rename_ref(refs, oldref, newref, msg);
	free(msg);
	return retval;
}

/**
 * Rename an existing ref.
 *
 * @param oldref Name of existing ref to rename.
 * @param newref New name for the ref.
 * @param logmsg Log message for reflog.
 * @return 0 on success, non-zero on failure.
 */
int rename_ref(const char *oldref, const char *newref, const char *logmsg)
{
	return refs_rename_ref(get_main_ref_store(the_repository), oldref, newref, logmsg);
}

/**
 * Copy an existing ref to a new ref using the given ref_store.
 *
 * @param refs the ref_store to use for copying
 * @param oldref name of existing ref to copy
 * @param newref name of new ref to create by copying oldref
 * @param logmsg log message for reflog
 * @return 0 on success, non-zero on failure
 */
int refs_copy_existing_ref(struct ref_store *refs, const char *oldref,
			    const char *newref, const char *logmsg)
{
	char *msg;
	int retval;

	msg = normalize_reflog_message(logmsg);
	retval = refs->be->copy_ref(refs, oldref, newref, msg);
	free(msg);
	return retval;
}

/**
 * Copy an existing ref to a new ref.
 *
 * @param oldref Name of existing ref to copy.
 * @param newref Name of new ref to create by copying oldref.
 * @param logmsg Log message for reflog.
 * @return 0 on success, non-zero on failure.
 */
int copy_existing_ref(const char *oldref, const char *newref,
		      const char *logmsg)
{
	return refs_copy_existing_ref(get_main_ref_store(the_repository), oldref, newref, logmsg);
}
